백준/ Silver 1 문제 , 백준 파이썬 11286 , 절댓값 힙

백준/ Silver 1 문제 , 백준 파이썬 11286 , 절댓값 힙

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>

절댓값이 같은게 한개 이상일때 가장 작은 값을 출력하는 방식에서 시간이 좀 걸렸다.
이럴때는 튜플을 사용하면 된다는 것을 배웠다.

 

<문제 출처>

 

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

11286번: 절댓값 힙

------------------------------------------------------------------------------------------------------------------------------

 

 

heap 문제이므로 힙을 사용해서 풀어보자

 

import heqpq 를 해주고

 

시작한다.

 

 

이 문제에서 가장 핵심은 힙에 어떻게 push 를 하는 것이다.

 

그냥 push 되는대로 넣을 수도 있겠지만 그럴때는 나중에 절댓값이 동일한 숫자들중에 작은 값을 가려내기가 쉽지가 않다.

 

애초에 heap 에 저장할때 가장 작은 값을 왼쪽에다가 배치시켜가면서 정렬해주면 출력시킬때도 왼쪽에서 하나씩 내보내면 된다.

 

이 아이디어를 사용할 수 있는게 바로 heap에다 튜플로 저장하는 것이다.

 

 

 

이렇게 heap 에다가 (절대값, 원래값) 으로 넣어주면

 

첫번째 기준을 절댓값으로 잡고 절대값에따라 배치를 한다.

 

이후 두번째 기준은 원래값으로 절댓값이 동일하다면? 원래값으로 양수인지 음수인지 판별하여 음수가 왼쪽으로 배치되게 정렬을 한다.

 

------------------------------------------------------------------------------------------------------------------------------

 

예를 들어보자

 

 

2

-2

1

 

이렇게 3가지의 수를 집어넣는다면

 

처음에 (2, 2)

 

두번째 [(2, -2) , (2, 2)]

 

세번째 [(1, 1), (2, -2), (2, 2)] 

 

순으로 저장될 것이다.

 

이후 0을 만나게 되면

 

pop 을 해주는데 이미 절댓값으로 기준을 나눈 상태이기 때문에 0번째 값을 무시하고 첫번째 값만 출력해주면 된다.

 

 

 

 

이때, 만약 heap 이 비어있다면 에러를 발생시키므로 try~except 구문으로 예외처리도 해주면 된다.

 

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답