이 문제는 내가 "어떠한 특정 알고리즘을 사용해서 풀었어요!!" 라는 말을 하고 싶어서 포스팅 하는 것이 아니다.
내가 말하고싶은 것은 다음과 같다.
Swift로 우선순위 큐 어떻게 짜는지
또 서로 다른 우선순위 큐를 어떻게 하나의 우선순위 큐 함수로 해결할지
나는 이러한 물음에 대한 답으로, Closure를 엮어서 이야기를 풀려고 한다.
먼저 문제의 요지를 알아보자.
문제는 주어지는 어떠한 홀수 개의 원소를 포함하는 배열에 대하여, 하나씩 원소들을 처리할 때 처리하는 원소의 갯수가 홀수인 순간에서의 중앙값을 보고자 한다.
말을 어렵게 풀어썼는데 요는 다음과 같다.
[1, 2, 3, 4, 5]
라는 배열이 있다고 가정하자.
처음 원소 1을 처리할때는 1이 유일한 값이고, 최소, 최대 이자 중앙값이다.
그리고 차례대로 처리하는 숫자가 1다음 홀수인 3개가 될 때까지 처리하게 되면 1, 2, 3을 처리하게 되는데, 이때의 중앙값은 2가 된다.
이런식으로 계속해서 원소를 처리할때마다 중앙값을 지정 하면된다.
여기서 중앙값을 지정하는 방식에 대해 생각을 해보면
[ M I N H E A P ] 중앙값 [ M A X H E A P ]
의 막대로 생각해볼수 있는데, 다음에 처리 할 원소의 크기가 중앙값에 비교하여 더 크면 MINHEAP, 작으면 MAXHEAP 으로 보내는 과정을 반복하면서 MINHEAP & MAXHEAP 의 밸런스에서 나오는 중앙값을 획득한다.
대략적인 문제의 설명은 다 했다.
그러면 내가 하고싶은 말의 본 요지인 HEAP 을 보자.
struct heap {
var lastn = 0
var heap : [Int] = []
init(_ size: Int) {
lastn = 0
heap = [Int](repeating: 0, count: size)
}
mutating func push(_ input: Int, comp: (_ s1: Int,_ s2: Int) -> Bool) {
self.lastn += 1
heap[self.lastn] = input
var C = lastn, P = C / 2
while P > 0 && !comp(heap[P], heap[C]) {
let temp = heap[P]; heap[P] = heap[C]; heap[C] = temp
C = P
P = C / 2
}
}
mutating func pop(comp: (_ s1: Int,_ s2: Int) -> Bool) {
heap[1] = heap[self.lastn]
self.lastn -= 1
var P = 1, L = 2, R = 3, C = 0
while L <= self.lastn {
if R > lastn {
C = L
}else {
C = comp(heap[L], heap[R]) ? L: R
}
if comp(heap[P], heap[C]){
break
}
let temp = heap[P]; heap[P] = heap[C]; heap[C] = temp;
P = C; L = P * 2; R = L + 1
}
}
}
아마 흔히 보는 HEAP 짜는 방식일텐데 위와 같이 짜게 되면 O(logN) 으로 push, pop이 가능해지게 된다.
그리고 위의 코드에서 보듯 이 HEAP 구조체는 Min, Max의 성질을 선택에 따라 가질수 있게 하고싶었다.
그래서 사용한게 바로 Closure이다.
mutating func push(_ input: Int, comp: (_ s1: Int,_ s2: Int) -> Bool)
이런식으로 Parameter로 전달하는 comp를 Closure로 사용할수 있게끔 만들어놨다. 번거롭고 낭비적으로 두가지 따로 생성하지말고 closure로 선택할수 있게끔 만드는 것을 해보고 싶었다.
let compmax = { (_ s1: Int, _ s2: Int) -> Bool in
return s1 >= s2
}
let compmin = {(_ s1: Int, _ s2: Int)->Bool in
return s1 <= s2
}
위와 같은 비교식을 만들어서 heap 의 목적에 맞게 사용하면 문제를 간단하게 풀수있다.
전체 코드는 여기에있다.