백준 1021번: 회전하는 큐 - Swift 풀이

오늘의 문제

1021번: 회전하는 큐

문제 제목 보고 순환 큐로 풀 생각에 front, rear 변수 두고 풀다가 괜히 뺑뺑 돌아 결국 제자리로 오게 된 사연...

실버 3인데 며칠 동안 풀었다...^^

태초부터 다시 시작했더니 금새 풀렸다.

 

내 풀이

import Foundation

let input = readLine()!.split(separator: " ").map { Int($0)! }
let N = input[0]
var count = 0

var numbers = readLine()!.split(separator: " ").map { Int($0)! }
var queue: [Int] = []

for i in 1...N {
    queue.append(i)
}

while true {
    // 다 뽑아냈으면 반복문 종료
    if numbers.isEmpty {
        break
    }
    if let idx = queue.firstIndex(of: numbers[0]) {
        if queue[0] != numbers[0] {
            // 왼쪽으로 이동하는 게 더 빠르면
            if idx <= abs(idx - (queue.count - 1)) {
                for _ in 0..<idx {
                    // 왼쪽으로 한 칸 이동
                    queue.append(queue.first!)
                    queue.removeFirst()
                    count += 1
                }
            } else { // 오른쪽으로 이동하는 게 더 빠르면
                for _ in 0...abs(idx - (queue.count - 1)) {
                    // 오른쪽으로 한 칸 이동
                    queue = Array(arrayLiteral: queue.last!) + queue
                    queue.removeLast()
                    count += 1
                }
            }
        } else {
            // 첫 번째 원소 뽑아내기
            queue.removeFirst()
            numbers.removeFirst()
        }
    }
}

print(count)

 

이 문제에서 매우 주관적인 핵심을 뽑아보자면,

1. 일단 난 처음에 Circular queue인 줄 알고 큐의 맨 앞을 가리키는 front 변수랑 맨 뒤를 가리키는 rear 변수를 두고 막 [front % queue.count] 뭐 이런 짓거리를 하면서 풀어보려고 했는데... 그럴 필요가 없었다는 것.을 깨닫는 것. 그냥 코드 싹 다 지우고 문제를 다시 봤더니 그 변수가 필요가 없겠더라.
2. 오른쪽으로 한 칸 이동할 때 큐의 맨 오른쪽 값 하나를 Array 형태로 만들어서 덧셈을 통해 queue의 앞에 합치는 코드. 이럴 생각을 맨 처음에 못 해서 front랑 rear를 두는 쓸데없는 짓을 시작했던 것 같다. 그냥 이렇게 배열을 합치고 맨 뒤에 값 없애면 모든 원소가 오른쪽으로 한 칸씩 이동된다.
3. 22번째 줄에  if idx <= abs(idx - (queue.count - 1)) 이 구문에서 등호(=)를 붙인 것. 이건 원래는 =을 안 붙이고 < 로 해둔 상태였는데 맨 마지막 예제 입력 4를 넣다가 알게 된 것이다.
   큐가 [ 10, 4, 5 ] 이렇게 있을 때 현재 빼내려는 숫자가 4이면 4가 딱 중간에 있어서 < 로 해둔 코드에서는 idx 값도 1, abs(idx - (queue.count - 1)) 값도 1로 동일해져서 else문에 걸리게 된다. 그럼 오른쪽으로 이동해서 [ 5, 10, 4 ] 이렇게 되고, 여기서 오른쪽으로 한 번 더 가야만 4가 맨 앞으로 오게 된다. 근데 이러지 말고 그냥 바로 왼쪽으로 가면 [ 4, 5, 10 ] 이 돼서 한 번의 이동만에 4를 뽑아낼 수 있잖아? 왼쪽으로 이동, 오른쪽으로 이동 간의 거리 비교도 중요하지만 맨 앞으로 와야만 뽑아낼 수 있다는 사실. 이에 대한 가중치를 if문의 등호(=)로 둔 것이다! 깨닫고 나서 무릎을 탁.

1번과 2번을 깨닫게 된 과정