[백준] 1655.가운데를 말해요 (Swift)

[백준] 1655.가운데를 말해요 (Swift)

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

1655번: 가운데를 말해요

풀이

시간복잡도를 고려해야하기 때문에 힙을 사용하는 문제입니다.

 

풀이를 위해선 최대힙과 최소힙을 모두 사용하는데, Swift 는 힙 자료구조를 제공하지 않아 직접 구현해야 합니다.

 

힙에 관한 설명과 Swift 를 이용해 작성된 코드는 아래 링크에서 확인하실 수 있습니다.

 

https://trumanfromkorea.tistory.com/42

[자료구조] Swift 로 Heap 구현하기

 

중간값을 찾기 위해서 최소힙과 최대힙에 번갈아가며 원소를 삽입해줍니다.

 

이 때 최대힙의 모든 원소가 최소힙보다 작은 값을 유지하도록 신경써주는것이 핵심입니다.

 

그렇게 된다면 최대힙의 루트노드는 최소힙보다는 작지만, 최대힙의 다른 모든 노드들보다 큰 값을 가지기 때문에 중간값을 도출해낼 수 있습니다.

 

힙의 원소 삽입과 삭제는 O(logN) 의 시간복잡도를 가지기 때문에 단순히 정렬하여 중간값을 뽑는 것 보다 효율적으로 문제를 풀이할 수 있습니다.

코드

	import Foundation
	var maxHeap: Heap<Int> = Heap(compare: >)
	var minHeap: Heap<Int> = Heap(compare: <)
	let n: Int = Int(readLine()!)!
	var answer: String = ""
	for i in 1 ... n {
	let input: Int = Int(readLine()!)!
	if i % 2 == 0 {
	minHeap.insert(n: input)
	} else {
	maxHeap.insert(n: input)
	}
	if minHeap.root == nil {
	answer += "\(maxHeap.root!)\n"
	continue
	}
	let maxRoot: Int = maxHeap.root!
	let minRoot: Int = minHeap.root!
	if maxRoot > minRoot {
	minHeap.heap[0] = maxRoot
	maxHeap.heap[0] = minRoot
	}
	if i % 2 == 0 { maxHeap.shiftDown(i: 0) }
	else { minHeap.shiftDown(i: 0) }
	answer += "\(maxHeap.root!)\n"
	}
	print(answer)

view raw BOJ_1655.swift hosted with ❤ by GitHub