백준 - 달팽이 리스트(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/17827

 

[문제 설명]

간단한 구현 문제. 단방향 사이클이 있는 그래프의 k번째 요소를 구하시오.

 

[접근 방법]

일정 주기로 사이클을 계속 돌기 때문에, 주기로 이동 횟수를 나누면 됨.

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    // 입력
    val (N,M,V) = readLine().split(" ").map {it.toInt()}
    val graph = readLine().split(" ").map { it.toInt() }.toIntArray()
    val sb = StringBuilder()

    repeat(M) {
        val c = readLine().toInt()

        // if : c가 그래프 크기보다 작으면, 해당하는 인덱스를 반환하면 됨.
        // else : c가 그래프 크기보다 크면, v~N까지 반복해서 도는 그래프가 됨.
        if (c <= N-1) {
            sb.append(graph[c])
        } else {
            // 남은 이동 횟수를 사이클로 나눈 나머지가 사이클에서 위치가 됨.
            // graph의 v-1이 사이클의 시작점이므로 v-1을 더해줌.
            val idx = (c-V+1)%(N-V+1)+V-1
            sb.append(graph[idx])
        }
        sb.append("\n")
    }

    println(sb)
}

시간복잡도는 StringBuilder의 append가 O(1)이므로 전체는 O(M)이 될 듯하다.