[BOJ] 백준 11286 절댓값 힙 (Swift)

문제

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

11286번: 절댓값 힙

풀이

최소 힙과 최대 힙 2개를 사용해서 풀이할 수 있는 문제입니다.
x가 양수라면 최소 힙에 넣어주고, x가 음수라면 최대 힙에 넣어줍시다.

그렇다면 최소 힙과 최대 힙에 절대값이 작은 수가 루트 노드에 위치할 것입니다.

pop을 해줄 때, 최소 힙과 최대 힙이 둘다 비어있다면, 0을 출력하고
최소 힙만 비어있다면 최대 힙에서 pop, 최대 힙만 비어있다면 최소 힙에서 pop 해줍시다.

둘다 비어있지 않다면, 최소 힙의 root와 최대 힙에 절대 값을 씌워서 절대 값이 더 작은 수를 pop 해줍시다.
최대 힙에는 음수가 들어있기 때문에 절대 값을 씌워서 비교하거나 -1을 곱해서 비교해주어야 합니다.

다른 방법으로는 Heap에 들어갈 요소를 커스텀해서 지정해주는 방법으로도 풀이할 수 있습니다.
절댓값과 본래의 수를 프로퍼티로 갖는 구조체를 정의하고, Comparable 프로토콜을 채택한 후
절댓값으로 비교를 하고, 절댓값이 같다면 원래 수가 더 작은 수로 비교해 주도록 구현해줍시다.

소스코드

후기

Heap을 약간 응용한 문제였습니다.