[Swift] 프로그래머스 이중우선순위큐

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

 

1. 문제 이해

일반적인 우선순위큐는 한 쪽 방향으로 Input, 다른 한 쪽 방향으로 Output이 이루어진다고 한다면, 문제에서 요구하는 이중우선순위큐는 Output이 양쪽 방향으로 이루어지는 형태이다. 큐에 데이터를 push하고 최댓값이나 최솟값을 pop할 수 있는 구조를 만들어야 한다.

 

 

2. 접근 방법

[정렬]

Output을 최솟값과 최댓값을 pop할 수 있는 형태로 큐를 만들어야 한다. 한 쪽은 최솟값만 다른 한 쪽은 최댓값만 pop할 수 있는 형태.

간단하게 정렬을 이용한다고 했을 때 오름차순을 기준으로 큐의 왼쪽(인덱스-0)은 최솟값, 큐의 오른쪽은(인덱스-N) 최댓값이 저장되어 있는 형태가 가능하다.

 

하지만 만약 그렇게 코드를 구현한다면 큐의 왼쪽 즉, 최솟값을 pop할 때 queue.removeFirst()는 시간 복잡도가 O(n)이기 때문에 비효율적인 것 같다.

 

요구하는 데이터가 최솟값이든 최댓값이든 O(1)인 queue.removeLast()를 사용할 수 있어야 한다.

 

최솟값일 때 큐를 내림차순 정렬하고, 최댓값일 때 큐를 오름차순 정렬하면 가능할 것이다.

 

3. 코드

import Foundation

func solution(_ operations:[String]) -> [Int] {
    var queue = [Int]()
    
    for operation in operations{
        let o = operation.split(separator: " ").map{String($0)}
        if o[0] == "I"{
            queue.append(Int(o[1])!)
        }else if o[1] == "1", !queue.isEmpty{
            queue.sort(by: <)
            queue.removeLast()
        }else if o[1] == "-1", !queue.isEmpty{
            queue.sort(by: >)
            queue.removeLast()
        }
    }
    return queue.isEmpty ?  [0,0] : [queue.max()!, queue.min()!]
}