[PS][BOJ][Swift] 중앙값 구하기

.onNext("Volga")·2021년 5월 6일
0

ProblemSolving

목록 보기
2/15

About "중앙값 구하기"

이 문제는 내가 "어떠한 특정 알고리즘을 사용해서 풀었어요!!" 라는 말을 하고 싶어서 포스팅 하는 것이 아니다.

내가 말하고싶은 것은 다음과 같다.

  • 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 의 목적에 맞게 사용하면 문제를 간단하게 풀수있다.

전체 코드는 여기에있다.

리뷰

  • Closure를 쓰는 가장 큰 목적은 함수를 간결하고 편하게 쓰기위해서인데, 지금 내가 짠 코드는 그런 목적을 가지고있진 않지 않은지?
  • Closure를 쓰긴썼는데, 프로토콜을 사용해서 목적에 맞게 꾸며나가는것도 괜찮진 않았을까
profile
iOS 개발자 volga입니다~

0개의 댓글