코딩테스트/BOJ

[백준][1021번] 회전하는 큐 - Kotlin(코틀린)

sinw212 2023. 8. 30. 16:32

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

  1.  첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ... ak 이었던 것이 a2, ... ak 와 같이 된다.
  2.  왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ... ak 가 a2, ... ak, a1 이 된다.
  3.  오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면 a1, ... ak가 ak, a1, ... ak-1 이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이 때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

입출력 예

10 3
1 2 3
//출력 0

10 3
2 9 5
//출력 8

32 6
27 16 30 11 6 23
//출력 59

10 10
1 6 3 2 7 9 8 4 10 5
//출력 14

코드(Kotlin) - 내 코드

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var st = StringTokenizer(readLine(), " ")
    val queSize = st.nextToken().toInt()
    val count = st.nextToken().toInt()
    st = StringTokenizer(readLine(), " ")
    
    val deque: Deque<Int> = LinkedList()
    for(i in 1 .. queSize) {
        deque.addLast(i)
    }
    
    var answer = 0
    for(i in 0 until count) {
        var num = st.nextToken().toInt()
        
        if(deque.indexOf(num) + 1 > deque.size / 2 + 1) {
            while(num != deque.peekFirst()) {
                deque.addFirst(deque.pollLast())
                answer++
            }
        } else {
            while(num != deque.peekFirst()) {
                deque.addLast(deque.pollFirst())
                answer++
            }
        }
        deque.pop()
    }
    println(answer)
    close()
}

 

풀이 과정

1. 해당 문제는 데크를 사용하여 접근하면 쉽게 풀 수 있다. 먼저 N개의 원소를 리스트에 추가해준다.

2. 왼쪽으로 한 칸 이동하는 연산은 아래 그림과 같이 첫번째 값을 마지막 위치에 추가해주면 된다.

deque.addLast(deque.pollFirst()

3. 오른쪽으로 한 칸 이동하는 연산은 아래 그림과 같이 마지막 값을 첫번째 위치에 추가해주면 된다.

deque.addFirst(deque.pollLast()

4. 여기서 주의해야 할 점은, 무작정 이동하는 것이 아닌 최소한으로 움직일 수 있는 방법을 찾아야한다.

그러기 위해서는 뽑아내고 싶은 원소의 위치가 리스트 길이의 절반보다 같거나 작다면 왼쪽으로 이동하는 연산을 하고 리스트 길이의 절반보다 크다면 오른쪽으로 이동하는 연산을 해야한다.

5. 뽑아내고 싶은 원소가 현재 리스트의 첫번째 값과 같아질 때 까지 한칸씩 이동하는 연산을 하여 최소 이동 횟수를 구할 수 있다.

 

문제의 제목에 현혹된 탓인지, 너무 당연하게도 환형 큐를 사용한 방식으로 문제에 접근했던 것 같다. 해당 방법으로 고민한 시간만해도 꽤 오랜 시간이 걸렸다. 데크를 사용하여 풀면 좋다는 힌트를 얻고서는 거의 단시간에 풀어낸 것 같다.

아직도 문제를 보자마자 어떤 방식으로 구현해야할지 한번에 머리에 떠오르지 않는 것을 보니, 더 다양하고 많은 문제를 풀며 감을 익히는 노력이 필요하다고 느꼈다.

저작자표시 (새창열림)