[백준] 11286. 구현_절댓값 힙- Python

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

★ 시작하기 전에

1. step별로 절댓값 처리된 리스트를 만든 후, 그 리스트만 다시 추려 최솟값을 빼는 방법

2. sorted함수를 이용하여 key 내에 두가지 기준으로 재정렬하는 방법

3. (이건 전혀 몰랐다..) heapq를 이용하는 방법 (ct. from queue import PriorityQueue 도 있음)

 

결국 1, 2 방법으로 시작하고 도전하고 실패했지만, heapq를 이용하라는 문제였다.

 

1차시도

import sys

input = sys.stdin.readline

n = int(input())

num_list = []
for i in range(n):
    m = int(input())
    if m != 0:
        num_list.append(m)
    else:
        if len(num_list)==0:
            print(0)
            continue
        else:
            abs_list = []
            for number in num_list:
                if number > 0:
                    abs_list.append(number)
                else:
                    abs_list.append(-number)
            min_number = min(abs_list)

            result = []
            for j in range(len(abs_list)):
                if abs_list[j] == min_number:
                    result.append(num_list[j])
            ans = min(result)
            num_list.remove(ans)
            print(ans)

min 함수 및 abs_list를 만든 점. 두번의 for문 등 시간초과가 날 수 밖에 없었던 코드... 내가봐도 난잡하다...

 

 

2차시도 (그래도 아는 함수좀 써봐야지)

import sys

sys.stdin = open('fight.txt','r')
input = sys.stdin.readline

n = int(input())

num_list = []
for i in range(n):
    m = int(input())
    if m > 0:
        num_list.append((m, m))
    elif m < 0:
        num_list.append((-m, m))
    else:
        if len(num_list)==0:
            print(0)
            continue
        else:
            num_list = sorted(num_list, key=lambda x:(-x[0], -x[1]))
            now = num_list.pop()
            print(now[1])

sorted 함수는 참 유용하다. sorted(배열하려는 literable, key=lambda x: @, [reverse=True]) 와 같이 @를 기준으로 정렬된다. 시간을 생각하는 문제에서는 시간을 잡아먹지만 난 이 방법도 마음에 든다.

 

 

3차시도 (heapq를 알고 사용한 방법)

import sys
import heapq


input = sys.stdin.readline

n = int(input())

num_list = []
for i in range(n):
    m = int(input())
    if m != 0:
        heapq.heappush(num_list, (abs(m), m))
    elif m == 0 and len(num_list) == 0:
        print(0)
    else:
        print(heapq.heappop(num_list)[1])

결국 heapq 모듈을 가져와서 사용하자. heapq는 O(logN) 시간복잡도를 가지며,

1. 리스트의 가장 앞 항목과 abs(m)를 우선 비교하여 정렬된다.

2. 같은 인덱스 0의 abs(m) 값들에 있어서는 m의 값을 기준으로 정렬된다.

전체 항목을 다 비교하지 않고 가장 앞의 항목과의 비교만 하여 정렬하기 때문에 최솟값, 최댓값 찾는데 이용!

 

※ 참고 시도 (PriorityQueue) - heapq에서 파생

import sys
from queue import PriorityQueue

input = sys.stdin.readline

n = int(input())

que = PriorityQueue()
ans = []
for _ in range(n):
    next = int(input())
    if next!=0:
        que.put((abs(next),next))
    elif not que.empty():
        ans.append(que.get()[1])
    else:
        ans.append(0)
print("\n".join(map(str, ans)))