11286. 절댓값 힙 (silver I)

✔️ 문제

11286번 문제 보기

✔️ 문제 분석 및 해결 과정 설계

• 문제 이해 :

  • 절댓값 힙 : 배열에 정수 x를 넣음 (x != 0)
  • 배열에서 절댓값이 가장 작은 값 출력, 그 값을 배열에서 제거
  • 절댓값이 가장 작은 값이 여러개일 경우 : 가장 작은 수 출력, 그 값을 배열에서 제거

• 입력 :

  • 첫째 줄 : 연산 개수 N (1 <= N <= 100,000)
  • N개의 줄 : 연산 정보 나타내는 정수 x 주어짐
    • x == 0 : 배열에 x를 넣는 연산
    • x != 0 : 배열에서 절댓값이 가장 작은 값 출력, 그 값을 배열에서 제거

• 출력 :

  • 입력에서 0이 주어진 횟수만큼 답 출력
  • 배열이 비어있는 상태에서 0이 입력될 경우 0 출력

사용할 자료구조 : 힙(우선순위 큐)
→ 대소관계를 비교할 수 있는 요소를 넣어야 정상적으로 동작하는 자료구조

자료를 정렬할 수 있는 함수 : sort()
ex) 튜플에 sort() 적용

arr = [(3, 4), (3, 1), (8, 5), (3, 2), (8, 10)]
arr.sort()
print(arr)
# [(3, 1), (3, 2), (3, 4), (8, 5), (8, 10)]

• sort()로 비교할 두가지
  • 절댓값의 대소 관계
  • 원본 값의 대소 관계

✔️ 문제 해결 과정

1️⃣ Priority Queue + Tuple을 사용한 풀이

1. N을 입력받은 뒤 N개의 x값을 입력

from heapq

for _ in range(int(input())):
    x = int(input())
    if x:
        # x가 0이 아닌 경우
    else:
        # x가 0인 경우

• Python은 기본 입출력 연산도 느린 편이므로 빠른 입출력연산을 사용해줌

from heapq
import sys

for _ in range(int(sys.stdin.readline())):
    x = int(sys.stdin.readline())
    if x:
        # x가 0이 아닌 경우
    else:
        # x가 0인 경우

• Tip : 빠른 입출력이 필요할 경우 코드 한 줄의 추가만으로 쉽게 변경 가능

from heapq
import sys

input = sys.stdin.readline
for _ in range(int(input())):
    x = int(input())
    if x:
        # x가 0이 아닌 경우
    else:
        # x가 0인 경우

2. priority queue에 Tuple형식으로 데이터 넣기

import heapq as hq
import sys

input = sys.stdin.readline
pq = []
for _ in range(int(input())):
    x = int(input())
    if x:
        hq.heappush(pq, (abs(x),x))
    else:
        print(hq.heappop(pq))

3. 0 입력 시 pq의 조건(empty여부) 확인

import heapq as hq
import sys

input = sys.stdin.readline
pq = []
for _ in range(int(input())):
    x = int(input())
    if x:
        hq.heappush(pq, (abs(x),x))
    else:
        if pq:
            print(hq.heappop(pq))
        else:
            print(0)

• 코드 간소화

import heapq as hq
import sys

input = sys.stdin.readline
pq = []
for _ in range(int(input())):
    x = int(input())
    if x:
        hq.heappush(pq, (abs(x),x))
    else:
        print(hq.heappop(pq) if pq else 0)

4. 원소를 튜플의 형태로 넣었기 때문에 튜플에서 추출할 요소를 지정해줌

import heapq as hq
import sys

input = sys.stdin.readline
pq = []
for _ in range(int(input())):
    x = int(input())
    if x:
        hq.heappush(pq, (abs(x),x))
    else:
        print(hq.heappop(pq)[1] if pq else 0)

2️⃣ Priority Queue + Priority Queue를 사용한 풀이

우선순위 큐 두개를 만들어 문제를 풀이할 수 있음

• min_heap = [] : 양수를 보관하는 힙 (원본 값이 가장 작은 값을 빼면 됨)
  • 양수는 절대값이 크면 원본 값도 큼
  • ex) 1, 2, 3, 8, 13, 99, 242
• max_heap = [] : 음수를 보관하는 힙 (원본 값이 가장 큰 값을 빼면 됨)
  • 음수는 절대값이 크면 원본 값은 더욱 작음
  • ex) -1, -4, -10, -1042

1. min_heap, max_heap에 값 저장

• 최대 힙을 구현하는 방법 : 매우 간단 ! hq.heappush(max_heap, -x)

import heapq as hq
from heapq import heappop, heappush
import sys

input = sys.stdin.readline
min_heap = [] # 양수 저장 힙
max_heap = [] # 음수 저장 힙

for _ in range(int(input())):
    x = int(input())
    if x: # x != 0
        if x > 0: # x가 양수인 경우
            hq.heappush(min_heap, x)
        else: # x가 음수인 경우
            hq.heappush(max_heap,x)

    else: # x == 0

2. x=0인 경우 min_heap, max_heap의 empty여부 고려

min_heap : empty O max_heap : empty O 0 출력	min_heap : empty X max_heap : empty O min_heap[0] 출력
min_heap : empty O max_heap : empty X max_heap[0] 출력	min_heap : empty X max_heap : empty X 둘 중 절댓값이 작은 쪽 출력 같으면 max_heap[0] 출력

import heapq as hq
from heapq import heappop, heappush
import sys

input = sys.stdin.readline
min_heap = [] # 양수 저장 힙
max_heap = [] # 음수 저장 힙

for _ in range(int(input())):
    x = int(input())
    if x: # x != 0
        if x > 0: # x가 양수인 경우
            hq.heappush(min_heap, x)
        else: # x가 음수인 경우
            hq.heappush(max_heap,-x)

    else: # x == 0
        if min_heap:
            if max_heap:
                if min_heap[0] < abs(max_heap[0]):
                    print(hq.heappop(min_heap))
                else:
                    print(-hq.heappop(max_heap))
            else:
                print(hq.heappop(min_heap))
        else:
            if max_heap:
                print(-hq.heappop(max_heap))
            else:
                print(0)

💡 회고

본 문제는 되게 어렵게 느껴졌다.
문제의 이해는 쉬웠으나 로직을 짜는 부분에서 어떤 자료구조를 사용해야 하는지, 어떤 로직을 짜야하는지 고민을 많이 하게 되었던 문제였던 것 같다.
절대값과 원본값을 동시에 비교해줘야 한다는 점을 문제 분석 단계에서 이해하고 있었지만,
이를 코드로 구현하기 위해서 어떻게 처리해줘야 할지 생각해내는 과정에서 어려움이 있었다.
풀이 과정을 통해 우선순위 큐 + 튜플을 사용하는 방법과 우선순위 큐 + 우선순위 큐를 사용하는 방법이 있음을 깨달았고,
본인은 튜플을 사용해 (절댓값, 원본값)의 형태로 넣어주는 방법이 보다 직관적이고 간단하게 로직을 구현할 수 있었다고 생각한다.

두번째 풀이 방법이었던 min_heap과 max_heap을 사용한 문제 풀이에서는,
두 우선순위큐의 empty 여부에 따른 네가지 케이스를 고려해줄 필요가 있었다.

else: # x == 0
    if min_heap and max_heap: # min & max : empty X
        if min_heap[0] < abs(max_heap[0]):
            print(hq.heappop(min_heap))
        else :
            print(-hq.heappop(max_heap))
    elif min_heap and len(max_heap) == 0: # min : empty X, max : empty O
        print(hq.heappop(min_heap))
    elif len(min_heap) == 0 and max_heap: # min : empty O, max : empty X
        print(-hq.heappop(max_heap))
    else:
        print(0)

위와 같이 조건을 한 눈에 파악하기 힘들게 나열하였기에 본인 스스로도 헷갈리는 상황이 발생했고,
그로부터 로직을 잘못 적용하는 실수를 저질렀다.
위 코드를 아래와 같이 작성해 개선하니 보다 가독성이 높아졌다.

else: # x == 0
    if min_heap:
        if max_heap:
            if min_heap[0] < abs(-max_heap[0]):
                print(hq.heappop(min_heap))
            else:
                print(-hq.heappop(max_heap))
        else:
            print(hq.heappop(min_heap))
    else:
        if max_heap:
            print(-hq.heappop(max_heap))
        else:
            print(0)

추후 문제 풀이에서는 보다 깔끔하고 직관적이게 코드를 작성하는 방법을 연습해야겠다.

또한 모든 문제에서 자료구조의 사용은 필수적이므로,
각 자료구조를 사용할 때 탐색, 삽입, 삭제의 시간 복잡도가 어떻게 되는지 파악하고 문제에 접근하는 능력을 길러야겠다.