백준 - 정보 상인 호석 - 22252 - swift

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

22252번: 정보 상인 호석

 

 

문제 유형은 우선순위 큐 이용 문제다. 

 

swift에서는 우선순위 큐가 없기 때문에, 이진 힙으로 이용하여 따로 구현해야 한다. 

몇 번 작성하다 보면은 저절로 외워진다. 

 

우선순위 큐가 필요한 이유는, 

쿼리가 다 주어진 다음에 계산을 시작하는 것이 아닌, 각 쿼리마다 그때그때 계산을 해야 한다.

한 번 거래한 정보는 호석이에게 더 이상 가치가 없기 때문에 고릴라도 그 정보를 파기한다.

어느 시점 때, 호석이가 고릴라에게 정보를 사면, 이후 시점부터는 해당 정보들은 존재하지 않는다.

또한 이후 시점부터 해당 고릴라가 또 다른 정보를 가져올 수 있다.  

그럼 이제 고릴라는 여러 새로운 정보들을 갖게 되고, 이후에 호석이가 또 그 고릴라로부터 정보를 사고자 한다면

새로운 정보들을 갱신한 상태에서 정보를 사야 할 것이다.

 

즉 , 각 쿼리마다 삽입 및 삭제가  빈번히 발생한다.

배열로 특정 위치에 삽입한다면 O(N)의 시간이 발생한다. 

 

이때 가치 순으로 가장 비싼 정보들을 구매한다.

또 호석이는 고릴라로부터 항상 비싼 정보들만 우선적으로 사기 때문에, 각 정보들은 항상 정렬되어 있어야 할 것이다.

 

그러므로 항상 정렬을 유지하면서, 삽입 및 삭제( O(logN) ) 도 빠른 시간 안에 가능한 우선순위 큐가 적합하다. 

 

import Foundation
struct Heap {
    var list = [Int]()
    var comparer: (Int, Int) -> Bool = (<)
    
    mutating func insert(_ x: Int ) {
        var idx = list.count
        list.append(x)
        while idx > 0, comparer(list[(idx-1)/2], list[idx]) {
            list.swapAt(idx, (idx-1)/2)
            idx = (idx-1)/2
        }
    }
    
    mutating func delete() -> Int? {
        if list.isEmpty { return nil }
        list.swapAt(0, list.count-1)
        let deleted = list.removeLast()
        var idx = 0
        var change = -1
        
        while idx < list.count {
            for k in idx*2+1...idx*2+2 {
                if k < list.count, comparer(list[idx], list[k]) {
                    if change == -1 || comparer(list[change], list[k]) {
                        change = k
                    }
                }
            }
            if change == -1 { break }
            list.swapAt(idx, change)
            idx = change
            change = -1
        }
        return deleted
    }
    var isEmpty: Bool { return list.isEmpty}
}

let Q = Int(readLine()!)!
var dict: [String: Heap] = [:]
var ans = 0
for _ in 0..<Q {
    let inp = readLine()!.split(separator: " " ).map{String($0)}
    if inp[0] == "1" {
        for i in 3..<inp.count {
            dict[inp[1],default: Heap()].insert(Int(inp[i])!)
        }
    } else {
        var chance = Int(inp[2])!
        let name = inp[1]
        if let _ = dict[name] {
            while !dict[name]!.isEmpty, chance > 0  {
                ans += dict[name]!.delete()!
                chance -= 1
            }
        }
    }
}
print(ans)