[알고리즘] Swift -백준 #23757 (아이들과 선물 상자)

문제링크

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

23757번: 아이들과 선물 상자

 

 

문제

상훈이는 N$N$개의 선물 상자를 가지고 있다. 선물 상자에는 현재 담겨있는 선물의 개수가 적혀있다.

선물을 받을 아이들이 M$M$명 있다. 아이들은 각자 1$1$에서 M$M$까지의 서로 다른 번호를 하나씩 부여받았다.

 1$1$번 아이부터 M$M$번 아이까지 한 번에 한 명씩, 현재 선물이 가장 많이 담겨있는 상자에서 각자 원하는 만큼 선물을 가져간다. 이 때, 앞서 누군가 선물을 가져갔던 선물 상자에서 또다시 가져가도 상관없다.

하지만 상자에 자신이 원하는 것보다 적은 개수의 선물이 들어있다면, 선물을 가져가지 못해 실망한다.

상훈이는 한 명이라도 실망하지 않고 모두가 선물을 가져갈 수 있는지 궁금하다.

입력

첫째 줄에 선물 상자의 수 N$N$ 과 아이들의 수 M$M$이 공백을 사이에 두고 주어진다. (1≤M≤N≤105$1\le M \le N\le 10^5$)

둘째 줄에 각 선물 상자에 들어있는 선물의 개수 c1,c2,…,cN$c_1,c_2,\ldots ,c_N$이 공백을 사이에 두고 주어진다. (1≤ci≤105$1\le c_i\le 10^5$)

셋째 줄에 아이들의 번호 순으로 각 아이가 원하는 선물의 개수 w1,w2,…,wM$w_1,w_2,\ldots ,w_M$이 공백을 사이에 두고 주어진다. (1≤wi≤105$1\le w_i\le 10^5$)

출력

모든 아이들이 실망하지 않고 각자 원하는 만큼 선물을 가져갈 수 있으면 1$1$을, 그렇지 않으면 0$0$을 출력한다.

 

 

---

분석

입력을 세줄을 받는다.

가장 많이 들어있는 선물상자를 찾아야한다. -> 우선순위큐를 만들어서 선물상자의 수만큼 반복문을 돌려서 힙에 넣어준다

아이들의 수만큼 반복을 돌려서 위에서 찾은 가장 큰 선물상자에서 아이들이 원하는 선물의 수를 빼준다.

위의 반복문서 만약 아이가 원하는 선물의 수가 가장 큰 선물상자의 수보다 크면 실망을 하기에 0을 출력

 

풀이

우선순위큐 구현 출처: https://beenii.tistory.com/143 [끄적이는 개발노트:티스토리]

class PriorityQueue<T> {
    private var heap: [T] = []
    private let comparing: (_ o1: T,_ o2: T) -> Bool
    
    init(_ comparing: @escaping (_ o1: T,_ o2: T) -> Bool) {
        self.comparing = comparing
    }
    
    func size() -> Int { heap.count }
    
    func isEmpty() -> Bool { heap.isEmpty }
    
    func clear() { heap.removeAll() }
    
    func peek() -> T? { heap.first }
    
    func push(_ value: T) {
        heap.append(value)
        if heap.count == 1 { return }
        var valueIndex = heap.count - 1
        var parentIndex = (valueIndex-1) / 2
        while !comparing(heap[parentIndex], heap[valueIndex]) {
            heap.swapAt(valueIndex, parentIndex)
            valueIndex = parentIndex
            parentIndex = (valueIndex-1) / 2
            if valueIndex == 0 { break }
        }
    }
    
    func pop() -> T? {
        if heap.count == 0 { return nil }
        if heap.count == 1 { return heap.removeFirst() }
        
        func isChildEmpty(_ value: Int,_ left: Int,_ right: Int) -> Bool {
            if heap.count <= left { return true }
            if heap.count > right { return false }
            if comparing(heap[value], heap[left]) { return true }
            heap.swapAt(value, left)
            return true
        }
        
        heap.swapAt(0, heap.count-1)
        let answer = heap.removeLast()
        
        var valueIndex = 0
        var leftIndex = valueIndex * 2 + 1
        var rightIndex = valueIndex * 2 + 2
        
        if isChildEmpty(valueIndex, leftIndex, rightIndex) { return answer }
        
        while !comparing(heap[valueIndex], heap[leftIndex]) || !comparing(heap[valueIndex], heap[rightIndex]) {
            let index = comparing(heap[leftIndex], heap[rightIndex]) ? leftIndex : rightIndex
            heap.swapAt(valueIndex, index)
            valueIndex = index
            leftIndex = valueIndex * 2 + 1
            rightIndex = valueIndex * 2 + 2
            
            if isChildEmpty(valueIndex, leftIndex, rightIndex) { break }
        }
        return answer
    }
}

let num = readLine()!.split(separator: " ").map{ Int($0) }
let gift = readLine()!.split(separator: " ").map{ Int($0) }
let idle = readLine()!.split(separator: " ").map{ Int($0) }

let pq = PriorityQueue<Int>() {
    return $0 > $1
}

for i in 0..<num[0]! {
    pq.push(gift[i]!)
}

var result = 1
for i in 0..<num[1]! {
    if idle[i]! > pq.peek()! {
        result = 0
        break
        
    } else {
        let first = pq.pop()!
        pq.push(first-idle[i]!)
    }
}

print(result)

 

결과

 

 

 

sort를 이용하여 아이들의 수만큼 계속 정렬을 해주게 되면

let num = readLine()!.split(separator: " ").map{ Int($0) }
var gift = readLine()!.split(separator: " ").map{ Int($0) }
let idle = readLine()!.split(separator: " ").map{ Int($0) }

var result = 1
for i in 0..<num[1]! {
    gift.sort(by: { $0! > $1! })
    if idle[i]! > gift[0]! {
        result = 0
        break

    } else {
        gift[0] = gift[0]!-idle[i]!
    }
}

print(result)

시간초과라는 것을 맛보게 된다 ㅎ