코딩테스트 연습 - 프린터

문제 풀이 아이디어

문제에서 주어진 프린터의 구조를 보면 맨 앞에 있는 문서부터 출력하는 것을 하지만 맨 앞의 문서가 최우선 중요도가 아니라면 프린터의 맨 뒤로 보냅니다. 즉 FIFO (First In First Out)의 자료구조인 Queue와 동일한 원리입니다.

따라서 해당 문제는 Queue로 구현해야 합니다. 하지만 Queue로 구현할 때 주의할 점이 있습니다. 바로 원래 프린터에 있던 처음 위치를 기억해야 한다는 점입니다. 따라서 enumerated를 통해서 처음 프린터에 있던 index와 값을 함께 저장합니다.

마지막으로 현재 프린트 맨 앞의 문서가 최중요도 문서인지 알아보기 위해서 priorities 배열을 정렬해서 가지고 있겠습니다. 이 배열의 last와 현재 Queue에 있는 맨 앞의 중요도와 비교해서 현재 출력할 차례인지 알 수 있습니다. 물론 출력하면 이 배열에서 popLast를 해야 합니다.

코드

// Swift로 큐 구현
struct Queue {
    private var queue = [(Int, Int)]()
    private var index = 0
    
    init(_ array: [Int]) {
        for (i, v) in array.enumerated() {
            self.queue.append((i, v))
        }
    }
    
    mutating func push(_ t: (Int, Int)) {
        queue.append(t)
    }
    
    mutating func pop() -> (Int, Int) {
        defer {
            index += 1
        }
        return queue[index]
    }
}

func solution(_ priorities:[Int], _ location:Int) -> Int {
    // 중요도를 정렬해서 별도의 배열
        // last가 최고 중요도
        // 최고 중요도 인쇄되면 pop
    var priorityRank = priorities.sorted()
    var printer = Queue(priorities)
    // 인쇄 횟수 count
    var cnt = 0
    
    while !priorityRank.isEmpty {
        // printer의 맨 앞에 있는 문서
        let now = printer.pop()
        
        // 최고 중요도 문서라면 출력
        if now.1 == priorityRank.last! {
            cnt += 1 //👉 출력 횟수 늘리고
            _ = priorityRank.popLast() //👉 중요도 배열에서도 pop
            if now.0 == location { return cnt } //👉그 문서가 location이라면 return
        // 최고 중요도가 아니라면 맨 뒤로 보내기
        } else {
            printer.push(now)
        }
    }
    
    return cnt
}

참고할 만한 블로그

둘 다 제 포스팅입니다. 하나는 Swift로 Queue를 구현하는 방법에 대한 것이고 다른 것은 백준의 유사한 문제를 풀이한 것입니다.

Swift로 Queue 구현하기

(Swift) 백준 1966 프린터 큐