문제 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
}'Problem Solving' 카테고리의 다른 글
| [SolveSQL] 쇼핑몰의 일일 매출액과 ARPPU (0) | 2025.02.06 |
|---|---|
| [SolveSQL] 배송 예정일 예측 성공과 실패 (0) | 2025.02.06 |
| [백준] 11286-절댓값 힙 (0) | 2025.02.05 |
| [백준] 1927-최소 힙 (0) | 2025.02.05 |
| [SolveSQL] 지역별 주문의 특징 (0) | 2025.02.05 |
