백준 17827 달팽이 리스트 코틀린[kotlin]

https://www.acmicpc.net/problem/17827

17827번: 달팽이 리스트

 

달팽이 리스트 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

1877

580

458

34.829%

문제

영진이는 달팽이를 좋아한다. 달팽이를 너무너무 좋아하기 때문에 특정한 모양의 단방향 연결리스트에 달팽이 리스트라는 이름을 붙여주었다.

일반적인 선형 단방향 연결리스트의 각 노드 번호를 연결된 순서대로 1, 2, ..., N이라 하자. 이때 N번 노드는 아무 노드도 가리키지 않는데, 여기서 N번 노드가 1번 노드를 제외한 임의의 노드를 가리켜 사이클을 이루게 되는 리스트를 달팽이 리스트라고 한다. 달팽이 리스트는 각 노드당 하나의 정수를 저장한다.

즉, 달팽이 리스트는 다음과 같이 생긴 연결리스트이다. 노드 안의 수는 저장된 값을 뜻한다.

"달팽아 달팽아 1번 노드부터 한 칸씩 총 K번 이동해 도착한 노드엔 어떤 값이 있을까?"

영진이는 어두운 방 안에서 달팽이 리스트 하나를 쓱쓱 그리더니, 같은 말을 K만 바꿔가며 계속 중얼거렸다.

영진이의 상태가 심상치 않아 보인다... 상황이 더 악화되기 전에 영진이의 모든 질문에 대답해주도록 하자.

입력

첫째 줄에 노드의 개수 N(2 ≤ N ≤ 200,000), 질문의 횟수 M(1 ≤ M ≤ 200,000), N번 노드가 가리키는 노드의 번호 V(2 ≤ V ≤ N)가 공백으로 구분되어 주어진다.

둘째 줄에 N개의 정수 C1, C2, …, CN이 공백으로 구분되어 주어진다. 이때 Ci는 i번 노드에 저장된 값을 뜻한다. (1 ≤ Ci ≤ 1,000,000)

셋째 줄부터 M개의 줄에 걸쳐 각 질문에 해당하는 K(1 ≤ K ≤ 109)가 주어진다.

출력

M개의 줄에 걸쳐 각 질문의 답을 출력한다.

예제 입력 1 복사

10 10 3
13 2 5 11 7 8 2 4 9 10
1
2
3
8
9
10
11
16
17
49

예제 출력 1 복사

2
5
11
9
10
5
11
9
10
10

힌트

물론 마지막 노드가 자기 자신을 가리키는 사이클을 가질 수도 있다.

영진이는 그런 달팽이 리스트를 민달팽이 리스트라고 부른다!

 

 

풀이

 

이 문제는 K가 N보다 큰 경우와 작은 경우에 따라 다른 로직으로 구현합니다

 

K가 N보다 작은 경우 그냥 배열에 접근하면 되지만 

 

K가 N보다 큰 경우 사이클이 존재하기 때문에 그 사이클에서 정확한 위치를 찾아내야 합니다

 

정확한 위치는

 

num[(k-T)%(N-T)+T]

 으로 표현 할 수 있는대 (T는 편하게 -1 시켰습니다 예시 -> T가 3인 경우 T-- 해서 2)

K에서 사이클에 해당하지 않는 부분을 뺀값(K-T)

전체 N에서 사이클에 해당하는 부분(N-T) 

을 나머지를 구한 다음 나머지 만큼 T와 더하면 해당 위치를 찾을 수 있습니다! 

fun main() = with(System.out.bufferedWriter()) {
    var(N,M,T) = readLine()!!.split(" ").map {it.toInt() }

    var num = readLine()!!.split(" ").map{it.toInt()}

    var sb = StringBuffer()
    T--
    for(i in 0 until M){
        var k = readLine()!!.toInt()
        if(k<N){
            sb.append(num[k])
            sb.append("\n")
        }else if(k==N){
            sb.append(num[T])
            sb.append("\n")
        }else{
            sb.append(num[(k-T)%(N-T)+T])
            sb.append("\n")
        }
    }

    println(sb.toString())
}