[백준] 11286번 : 절댓값 힙 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

11286번: 절댓값 힙

 

1. 문제 설명

2. 풀이과정

N의 최대 범위가 100,000이므로 O(nlogn) 시간 복잡도 알고리즘으로 해결할 수 있다.

데이터가 새로 삽입될 때마다 절댓값과 관련된 정렬이 필요하므로 우선순위 큐를 활용해 문제를 해결한다.

하지만 해당 문제는 절댓값에 대한 정렬이 필요하므로 우선순위 큐의 정렬 기준을 직접 정의해야 한다.

 

X = 0일 때, 큐가 비어 있으면 0을 출력한다.

X = 0일 때, 큐가 비어 있지 않으면 큐에서 절댓값이 최소인 값을 출력한다.

만약 절댓값이 같다면 음수를 우선으로 출력한다.

X != 0일 때, put()으로 큐에 새로운 값을 추가하고 우선순위 큐 정렬 기준으로 자동 정렬한다.

 

우선순위 큐 정렬 기준을 새로 적용하는 방법은 큐에 데이터를 추가할 때 정렬 기준을 순서대로 묶어 한 데이터의 형태로 추가하면 된다.

해당 문제에서는 절댓값을 기준으로 정렬되도록 설정하고, 절댓값이 같으면 음수를 우선으로 정렬하기 때문에 큐에 데이터를 추가할 때 (abs(X), X) 형태로 추가하면 앞에서부터 정렬 기준이 되어 절댓값을 기준으로 오름차순 정렬하고 절댓값이 같으면 음수와 양수 중 더 작은 순으로 오름차순 정렬되게 되므로 음수가 우선으로 정렬되게 된다.

 

슈도코드

1. N(질의 요청 개수) 입력받기
2. 우선순위 큐 queue 선언
3. for N만큼 반복
4. 요청이 0일 때 : 큐가 비어 있으면 0, 비어 있지 않으면 큐의 제일 앞 원소의 값 출력 get()
5. 요청이 0이 아닐 때 : 새로운 데이터를 우선순위 큐에 추가 put()
6. 절댓값 기준으로 정렬되도록 설정, 절댓값이 같으면 음수 우선 정렬 (abs(X), X) 형태로 큐에 추가

반응형

3. 소스코드

import sys
from queue import PriorityQueue

N = int(sys.stdin.readline())

queue = PriorityQueue()
for _ in range(N):
    X = int(sys.stdin.readline())

    if (X == 0):
        if (queue.empty()):
            print(0)
        else:
            temp = queue.get()
            print(temp[1])
    else:
        queue.put((abs(X), X))