[Swift] 백준_프린터 큐(1966)

문제

 

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

1966번: 프린터 큐

 

 

풀이

 

큐를 이용해서 풀 수 있는 문제였다.

 

프린터 큐를 돌리며 가장 큰 값인 경우에 출력하고, 그 값을 큐에서 제거하는 것을 반복해주었다. 타겟이 아닌 문서가 큐에서 제거될때마다 count값을 증가시켜주었고, 타겟의 인덱스를 1씩 감소시켜주었다.

 

타겟의 인덱스가 0이고, 타겟이 큐에서 가장 큰 값일때의 count를 출력하였다.

 

배열에서 max값을 구하는 것은 O(N)인데 프린터가 될때마다 max값이 바뀌어서 시간이 더 많이 들거라고 생각했다. 그래서 while문 이전에 한 번의 오름차순 정렬을 통해 배열을 만들고 last와 removeLast()를 이용하였다.

import Foundation

let caseCount = Int(readLine()!)!
for _ in 0..<caseCount {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    var priority = readLine()!.split(separator: " ").map { Int(String($0))! }
    var sorted = priority.sorted(by: <)
    var target = input[1]
    var count = 1
    while true {
        if priority[0] == sorted.last! {
            if target == 0 {
                print(count)
                break
            }
            priority.removeFirst()
            sorted.removeLast()
            count += 1
            target -= 1
        } else {
            priority.append(priority.removeFirst())
            target = target == 0 ? priority.count - 1 : target - 1
        }
    }    
}

 

 

_____________________________________________________________________________________________________

 

큐를 이용할땐 시간복잡도를 조금 더 생각해보자.