백준 1202 보석 도둑

출처: www.acmicpc.net/problem/1202

분류: 우선순위 큐, 그리디

---

접근방식

진짜 어마무시하게 틀렸던 문제입니다... 

보석과 가방을 모두 오름차순으로 정렬해두고

가방에 담을 수 있는 보석들을 우선순위 큐에 담아서 가장 비싼 보석을 넣어주면 되는 문제였습니다.

핵심이 되는 코드 부분만 보시면 이해하실 수 있을거에요 :)

var jamIdx = 0
for back in backs {
    while jamIdx < jams.count, jams[jamIdx].m <= back {
        heap.insert(jams[jamIdx])
        jamIdx += 1
    }
    
    let jam = heap.remove()
    getValue += jam?.1 ?? 0
}

 

우선순위 큐 힌트를 얻고도 어떻게 사용해야 할지 감을 못 잡았었네요.. 

 

해결방법

public struct Heap<T> {
    
    private var nodes = [T]()
    
    private var orderCriteria: (T, T) -> Bool
    
    public init(sort: @escaping (T, T) -> Bool) {
        // 최대 힙인지 최소 힙인지 기준을 잡는다.
        self.orderCriteria = sort
    }
    
    public init(array: [T], sort: @escaping (T, T) -> Bool) {
        self.orderCriteria = sort
        configureHeap(from: array)
    }
    
    public var isEmpty: Bool {
        return count == 0
    }
    
    public var count: Int {
        return nodes.count
    }
    
    public func peek() -> T? {
        return nodes.first
    }
    
    public mutating func insert(_ value: T) {
        nodes.append(value)
        shiftUp(nodes.count - 1)
    }
    
    public mutating func remove() -> T? {
        guard !nodes.isEmpty else { return nil }
        
        if nodes.count == 1 {
            return nodes.removeLast()
        } else {
            let value = nodes[0]
            nodes[0] = nodes.removeLast()
            shiftDown(0)
            return value
        }
    }
    
    public mutating func remove(at index: Int) -> T? {
        guard index < nodes.count else { return nil }
        
        let lastIndex = nodes.count-1
        if index != lastIndex {
            nodes.swapAt(index, lastIndex)
            shiftDown(from: index, until: lastIndex)
            shiftUp(index)
        }
        
        return nodes.removeLast()
    }
    
    // 변수를 직접 변경해야 하기 때문에 mutating 을 사용한다.
    private mutating func configureHeap(from array: [T]) {
        nodes = array
        
        /**
         * 힙 트리에서 n/2 - 1 은 하나 위 층위가 된다.
         * shiftDown을 하면서 자리를 잡을 것이기 때문에
         * 마지막 leaf 노드들은 할 필요가 없다.
         */
        for i in stride(from: nodes.count/2 - 1, through: 0, by: -1) {
            shiftDown(i)
        }
    }
    
    private func parentIndex(ofIndex i: Int) -> Int {
        return (i - 1) / 2
    }
    
    private func leftChildIndex(ofIndex i: Int) -> Int {
        return 2*i + 1
    }
    
    private func rightChildIndex(ofIndex i: Int) -> Int {
        return 2*i + 2
    }
    
    /**
     * shiftUp은 자신과 부모를 비교해 바꿔준다.
     */
    private mutating func shiftUp(_ index: Int) {
        var childIndex = index
        let child = nodes[childIndex] // 처음에 노드를 저장해두고 인덱스를 구한 후 바꿔준다.
        var parentIndex = self.parentIndex(ofIndex: index)
        
        while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
            nodes[childIndex] = nodes[parentIndex]
            childIndex = parentIndex
            parentIndex = self.parentIndex(ofIndex: childIndex)
        }
        
        nodes[childIndex] = child
    }
    
    /**
     * shiftDown은 left, right 자식 중 적합한 녀석이 있으면 바꾸면서 바닥까지 내려간다.
     */
    private mutating func shiftDown(from index: Int, until endIndex: Int) {
        let leftChildIndex = self.leftChildIndex(ofIndex: index)
        let rightChildIndex = leftChildIndex + 1
        
        var first = index
        if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
            first = leftChildIndex
        }
        if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
            first = rightChildIndex
        }
        if first == index { return }
        
        nodes.swapAt(index, first)
        shiftDown(from: first, until: endIndex)
    }
    
    private mutating func shiftDown(_ index: Int) {
        shiftDown(from: index, until: nodes.count)
    }
    
}

let nk = readLine()!.split(separator: " ").map { Int(String($0))! }
var jams = [(m: Int, v: Int)]()
var backs = [Int]()

for _ in 0..<nk[0] {
    let d = readLine()!.split(separator: " ").map { Int(String($0))! }
    jams.append((d[0], d[1]))
}
for _ in 0..<nk[1] {
    backs.append(Int(readLine()!)!)
}

jams.sort(by: { $0.m < $1.m })
backs.sort(by: <)
var heap = Heap<(Int, Int)>(array: [], sort: { $0.1 > $1.1 })
var getValue = 0

var jamIdx = 0
for back in backs {
    while jamIdx < jams.count, jams[jamIdx].m <= back {
        heap.insert(jams[jamIdx])
        jamIdx += 1
    }
    
    let jam = heap.remove()
    getValue += jam?.1 ?? 0
}

print(getValue)

 

배운점

제출을 보니 9달 전에 어마어마하게 깨지고 포기했던 문제.

역시나 이번에도 비슷하게 접근해서 또 틀렸었다;; 그래도 이번엔 다른 분들 풀이 보고 이해하긴 했네..... 휘유...