99클럽 코테 스터디 24일차 TIL: 최대 힙 + 그리디

문제

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

풀이

1번 기호가 나머지 기호보다 많은 투표수를 받도록 해주어야 한다.
최소 표를 구해야 한다.

나머지 후보들 중에서 가장 득표를 많이받은 후보의 표를 뺏어와야 하므로, 최대값을 뽑아야하는데
최대힙을 구현하면 빠르게 최대값을 구현할 수 있다.

최대힙에서 pop 연산을 하고, 뽑은 요소에 -1을 해주어 다시 최대 힙에 넣어주고
1번 기호의 표를 + 1 해준다.

이를 반복하며 1번 기호가 최대힙에서 뽑은 요소보다 득표수가 많다면 종료해주면 되는 문제

소스코드

	struct Heap<T: Comparable> {
	private var elements: [T] = []
	private let comparer: (T, T) -> Bool
	init(comparer: @escaping (T,T) -> Bool) {
	self.comparer = comparer
	}
	mutating func insert(element: T) {
	if elements.isEmpty {
	elements.append(element)
	elements.append(element)
	return
	}
	elements.append(element)
	swimUp(index: elements.count - 1)
	}
	mutating private func swimUp(index: Int) {
	var index = index
	while index > 1 && comparer(elements[index], elements[index / 2]) {
	elements.swapAt(index, index / 2)
	index /= 2
	}
	}
	mutating func pop() -> T? {
	if elements.count < 2 { return nil }
	elements.swapAt(1, elements.count - 1)
	let deletedElement = elements.removeLast()
	diveDown(index: 1)
	return deletedElement
	}
	mutating private func diveDown(index: Int) {
	var swapIndex = index
	var isSwap = false
	let leftIndex = index * 2
	let rightIndex = index * 2 + 1
	if leftIndex < elements.endIndex && comparer(elements[leftIndex], elements[swapIndex]) {
	swapIndex = leftIndex
	isSwap = true
	}
	if rightIndex < elements.endIndex && comparer(elements[rightIndex], elements[swapIndex]) {
	swapIndex = rightIndex
	isSwap = true
	}
	if isSwap {
	elements.swapAt(swapIndex, index)
	diveDown(index: swapIndex)
	}
	}
	}
	var n = Int(readLine()!)!
	var me = Int(readLine()!)!
	var maxHeap = Heap<Int>(comparer: >)
	var result = 0
	for _ in 0..<n-1 {
	maxHeap.insert(element: Int(readLine()!)!)
	}
	while true {
	guard let element = maxHeap.pop() else { break }
	if me > element {
	break
	}
	result += 1
	maxHeap.insert(element: element - 1)
	me += 1
	}
	print(result)

view raw 1417_국회의원 선거.swift hosted with ❤ by GitHub

후기

작곡 레슨이 있어서 빠르게 비기너 문제를 풀이했다. 쉽게 풀 수 있었던 문제