백준 1966번 프린터 큐 - 스위프트(Swift) 풀이

 배열로 환형 큐를 구현하면 된다. front를 현재 맨 앞에 있는 문서를 가리키는 포인터라고 하면, 

1. 앞에서 뽑은 것을 다시 맨 뒤에 넣기 : 그냥 front를 하나 뒤로 옮기면 저절로 된다!
2. 인쇄하기 : 해당 자리에 인쇄 표시를 하고 front를 뒤로 하나 옮긴다. (다음에 front가 이 자리에 오면 없는 셈 치고 스킵하면 됨)
3. 인쇄해야할 대상인지 판단 : 우선순위들을 정렬한 배열을 따로 둬서 남은 문서 중 우선순위 최댓값을 알 수 있도록 한다.

 

---

1. 앞에서 뽑은 것을 다시 맨 뒤에 넣기

 front를 하나 뒤로 옮기면, 그 다음 문서가 front가 되고, 현재 문서는 front의 바로 왼쪽으로 가게 된다. front를 계속 우측으로 한 칸씩 이동시킬 것이므로, front의 바로 왼쪽에 있다는 것은 가장 마지막에 방문하게 될 것이라는 뜻이다. 따라서 맨 뒤로 보낸 것과 같은 효과이다.

 front가 맨 마지막에 도달했을 경우, 다음이 없으므로 다시 맨 앞으로 가줘야 하는데, 이 부분을 front == N-1 ? 0 : front + 1로 구현해줬다.

 

2. 인쇄하기

 배열에서 진짜로 제거하지 않고, 인쇄됐다는 표시만 해둔다. 아래 코드에서는 isDone으로 표시했다. 나중에 front가 인쇄된 문서를 가리키면 그냥 스킵해버리면 된다.

 

3. 인쇄해야할 대상인지 판단

 현재 큐에 남아있는 문서 중 우선순위가 최댓값인 것만 인쇄할 수 있다. 따라서 항상 남은 문서 중 우선순위의 최대값을 알고 있어야 한다. 아래 코드에서는 sortedPriorities라는 오름차순으로 정렬된 배열을 따로 두고, 인쇄할 때마다 popLast()를 해주었다. 오름차순 정렬되어있으므로 last는 최댓값이고, 인쇄하는 문서는 항상 최댓값을 가지기 때문!

 

---

import Foundation

struct Document {
    let index: Int
    let priority: Int
    var isDone: Bool = false
}

func solution(N: Int, M: Int, priorities: [Int]) -> Int {
    var queue = priorities.enumerated().map{ Document(index: $0, priority: $1) }
    var sortedPriorities = priorities.sorted()
    
    var front = 0
    var count = 0
    
    while true {
        while queue[front].isDone {                 // 이미 인쇄한 문서들 스킵
            front = front == N - 1 ? 0 : front + 1
        }
        
        let currentDoc = queue[front]
        let maxPriority = sortedPriorities.last!
        
        if currentDoc.priority < maxPriority {      // 현재 문서보다 중요한 문서가 있는 경우
            front = front == N - 1 ? 0 : front + 1  // 인쇄하지 않고 맨 뒤에 재배치
        } else {                                    // 현재 문서가 가장 중요한 문서인 경우
            count += 1
            queue[front].isDone = true              // 인쇄
            _ = sortedPriorities.popLast()          // 최대값 갱신
            
            if currentDoc.index == M { return count }
        }
    }
}

var result = ""

var testcase = Int(readLine()!)!
while testcase > 0 {
    let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    let priorities = readLine()!.split(separator: " ").map{ Int(String($0))! }
    let N = input[0]
    let M = input[1]
    
    let solution = solution(N: N, M: M, priorities: priorities)
    result.write("\(solution)\n")
    
    testcase -= 1
}

print(result)