[백준] 1715-카드 정렬하기

문제 URL

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

 

 

문제 설명 요약

• 최소힙을 활용하여 카드 묶음의 값 정렬
• 작은 값부터 꺼내고 더해가며 최소 비교 횟수 구하기

 

문제 풀이

• 최소힙 직접 구현 필요 (스위프트는 힙 자료구조 없음)
  • Heap :: push -> 추가되는 값을 힙 내 원소들과 비교하여 저장 
  • Heap :: pop -> 최소힙의 값(최상단 루트 값) 삭제 및 반환

 

Swift를 활용한 풀이

 

var heap = [0] // 1-based-index
let N = Int(readLine()!)!
for _ in 0..<N { push(Int(readLine()!)!) }

// 카드 묶음의 값을 두 개씩 꺼내어 합쳐나가는 과정 
// 합치는 것의 대상 두 묶음을 답에 누적 & 합쳐진 값은 새로운 카드 묶음으로 취급(push)
var answer = 0
while(heap.count > 2) {
    let a = pop()
    let b = pop()
    answer += a+b
    push(a+b)
}
print(answer)

// 힙에 원소 추가
// 1. 배열 맨 끝에 추가
// 2. 끝 인덱스 값을 시작으로 부모값과의 대소 비교 후, 부모값보다 작다면 스왑 수행
// 3. (2)번 작업을 idx가 1까지 줄어들기 전까지 진행함. 단, 그 이전에 부모값보다 큰 경우엔 탈출
func push(_ n:Int) {
    heap.append(n)
    if(heap.count == 2) { return }

    var idx = heap.count-1
    while(idx > 1) {
        let parent = idx/2
        if(heap[parent] <= heap[idx]) { break }
        heap.swapAt(parent, idx)
        idx = parent
    }
}

// 최소힙의 값 삭제(루트 삭제) 및 반환
// 1. 힙의 맨 끝의 값을 루트로 이동
// 2. 갱신된 루트값에 대하여 자식값 두 개와 비교 후, 더 작은 자식 값이 있는 경우 스왑 수행
// (2)번 작업을 자식 인덱스값이 배열 범위 내에 있는 경우에 한하여 진행. 단, 두 자식보다 부모의 값이 작은 경우엔 탈출
func pop() -> Int {
    if(heap.count == 1) { return 0 }

    let deleted = heap[1]
    heap[1] = heap[heap.count-1]
    heap.removeLast()

    var idx = 1
    while(idx*2 < heap.count) {
        let left = idx*2, right = idx*2+1
        var minIdx = left
        if(right < heap.count && heap[right] < heap[left]) { minIdx = right }

        if(heap[idx] < heap[minIdx]) { break }
        heap.swapAt(idx,minIdx)
        idx = minIdx
    }
    return deleted
}