1966번: 프린터 큐

문제 풀이 아이디어

# 사용해야 하는 자료구조 = queue
  : FIFO 방식을 사용하기 때문에 입출력을 O(1)으로 구현하기 위해서 Queue를 사용합니다.
  : 제일 높은 중요도를 찾기위해 탐색을 사용하기는 합니다만,
  : 어차피 순차적으로 다 따져야 하기 때문에 어떤 자료형을 쓰던 O(n)입니다.

# 문제 풀이 아이디어
  : 큐를 만들고 인쇄물들을 넣습니다. (처음에 들어온 순서 기록 by enumerated)
  : 지금 큐의 맨 앞에 있는 것을 프린트 가능한지 확인합니다.
    : 가장 높으면 인쇄
    : 높은거 있으면 뒤에 넣기

# 의사코드
  1. 입력 받는다.
  2. queue에 인쇄물을 넣습니다.
  3. 큐의 맨 앞 문서의 중요도를 확인해서
      3-1. 나머지 문서들 보다 중요도가 높으면 인쇄합니다.
          3-1-1. cnt += 1
      3-2. 나머지 문서들 보다 중요도가 낮으면 pop하고 push
  4. 출력된 문서가 M번째 문서라면 cnt를 출력합니다.

# 시간복잡도
  : 문서를 출력하거나 문서를 queue 맨 뒤로 보내는 동작은 O(1)
  : 다른 문서들과 중요도를 비교하는데 O(n) (순차탐색)
  : n이 최대 100이므로 시간 복잡도는 크게 신경쓸 필요가 없습니다.

코드

// 프린터 큐

//✅ 큐 구현
struct Queue {
    // index 큐를 사용 (N이 적으므로)
    var queue = [(Int, Int)]() //👉 처음 문서 위치를 기억해야하므로 (처음 위치, 중요도)의 튜플
    var index = 0
    
    // 입력을 받아서 튜플의 배열로 바꾸어 저장한다.
    init(_ array: Array<Int>) {
        for (i, num) in array.enumerated() {
            queue.append((i, num))
        }
    }
    
    var count: Int {
        return queue.count - index
    }
    
    //⭐️ 현재 맨 앞의 문서를 출력할 수 있는지
        //❗️ index를 queue일 경우 처음 문서는 queue[index]라는 점에 주의
    var isPrintable: Bool {
        if queue.count == 1 { return true } //👉 문서가 1개 뿐이면 true
        for i in (index + 1)..<queue.count { //👉 순차 탐색을 하면서
            if queue[i].1 > queue[index].1 { return false } //👉 더 중요한 문서가 있으면 false
        }
        return true
    }
    
    mutating func push(_ tuple: (Int, Int)) {
        queue.append(tuple)
    }
    
    mutating func pop() -> (Int, Int) {
        defer {
            index += 1
        }
        return queue[index]
    }
}

let T = Int(readLine()!)!

// 테스트 케이스 만큼 반복
for _ in 0..<T {
    let input1 = readLine()!.split(separator: " ").map { Int(String($0))! }
    let M = input1[1] //👉 추적하고자 하는 문서 위치
    let input2 = readLine()!.split(separator: " ").map { Int(String($0))! }
    var queue = Queue(input2)
    var cnt = 0 //👉 현재까지 출력된 문서 갯수
    while true {
        // 프린트가 가능하면
        if queue.isPrintable {
            let printed = queue.pop() //👉 프린트하고
            cnt += 1 //👉 갯수 추가
            if printed.0 == M { break } //👉 추적하는 문서인지 확인
        // 프린트 안되면
        } else {
            queue.push(queue.pop()) //👉 맨 뒤로 보내기
        }
    }
    print(cnt)
}

중요도만 별도의 배열로 관리

어차피 출력되는 문서의 순서는 중요도가 높은 순입니다. 따라서 중요도만 오름차순으로 정렬된 별도의 배열로 관리를 하는 방법입니다.

현재 pop한 문서의 중요도가 중요도 배열의 있는 last (= 현재 남은 문서 중에서 가장 높은 중요도)와 일치하면 중요도 배열의 last를 제거하고 프린트를 하는 방식입니다.

배열의 정렬 메소드는 O(nlogn)입니다. 기존의 방법은 O(n)의 탐색 메소드를 반복문 안에서 실행합니다. 따라서 시간 복잡도 관점에서 보면 꼭 어느 방법이 더 낫다고는 할 수 없습니다.

//✅ 큐 구현
struct Queue {
    // index 큐를 사용 (N이 적으므로)
    var queue = [(Int, Int)]() //👉 처음 문서 위치를 기억해야하므로 (처음 위치, 중요도)의 튜플
    var index = 0
    
    // 입력을 받아서 튜플의 배열로 바꾸어 저장한다.
    init(_ array: Array<Int>) {
        for (i, num) in array.enumerated() {
            queue.append((i, num))
        }
    }
    
    var count: Int {
        return queue.count - index
    }
    
    mutating func push(_ tuple: (Int, Int)) {
        queue.append(tuple)
    }
    
    mutating func pop() -> (Int, Int) {
        defer {
            index += 1
        }
        return queue[index]
    }
}

let T = Int(readLine()!)!

// 테스트 케이스 만큼 반복
for _ in 0..<T {
    let input1 = readLine()!.split(separator: " ").map { Int(String($0))! }
    let M = input1[1] //👉 추적하고자 하는 문서 위치
    let input2 = readLine()!.split(separator: " ").map { Int(String($0))! }
    var queue = Queue(input2)
    var priorities = input2.sorted() //👉 중요도를 오름차순으로 정리
    var cnt = 0 //👉 현재까지 출력된 문서 갯수
    while queue.count > 0 {
        let now = queue.pop()
        if now.1 == priorities.last {
            cnt += 1
            priorities.removeLast()
            if now.0 == M { break }
        } else {
            queue.push(now)
        }
    }
    print(cnt)
}