[11286번] 절댓값 힙

백준 11286번: 절댓값 힙

11286번: 절댓값 힙

이전 포스팅했던 글과 매우 유사합니다.

[여기]를 참고하여 Heap(또는 priority_queue)를 이해하고 거의 같은 문제라는 것을 보시기 바랍니다.

---

이 문제는 조금 생각을 해봐야 합니다. 이전에 보여드렸던 MAX 혹은 min Heap과는 달리 조건이 추가된 Heap을 만들어야 하기 때문입니다.

 

저는 처음에 조금 해맸습니다. 어떻게 하면 원본과 절댓값을 비교하여 Heap을 만들까를 말이죠.

그래서 struct를 통해 절댓값과 원본을 저장하여 비교함수를 통해 Heap을 돌리기로 했죠.

 

하지만 이렇게 하니 뭔가 잘 안되더군요.

그래서 새롭게 생각한 것이 좀 더 간단하게 이를 구현할 수 있는 pair<int, int> container를 이용하는 것이었습니다.

first 부분에는 절댓값의 음수를, second 부분에는 원본의 음수 값을 저장했습니다.

 

음수를 사용한 이유는 default Heap인 MAX Heap을 이용할 때 비교되는 부분은 pair의 first만 볼 것이니 절댓값이 작으면 작을수록 음수를 붙이면 큰 것으로 판단할 것이기 때문입니다.

이렇게 하고 제출하니 잘 맞았습니다.

 

하지만 지금 생각해보니 왜 second에도 음수를 붙였는지는 의문이군요. 딱히 없어도 될 것 같은 느낌이 듭니다만...

아무튼 가끔씩 pair Container를 까먹는데 중요하니 다시 한 번 상기시켜야 겠습니다. ㅎㅎ

 

[소스 보기]