7662

날짜 : 2023. 10. 10

사용 언어 : python

 

문제

 

코드

import sys
import heapq

INF = int(1e20)
def solution(operations):
    maxheap = list()
    minheap = list()
    hash = dict()
    cnt = 0  # 전체 큐에 남아있는 원소의 개수
    for temp in operations:
        op, num = temp.split()
        num = int(num)
        if op == "I":  # 삽입
            cnt += 1
            heapq.heappush(minheap, num)
            heapq.heappush(maxheap, num * (-1))
            if num not in hash: hash[num] = 1
            else: hash[num] += 1
            continue
        if cnt == 0: continue  # 더이상 뺄 수 없는 상태 => 추출 연산 패스
        cnt -= 1
        if num == -1:  # 최소값 추출
            while True:
                n = heapq.heappop(minheap)
                if hash[n] > 0:
                    hash[n] -= 1  # 뺄 수 있는 값인지 체크
                    break
        else:  # 최대값 추출
            while True:
                n = heapq.heappop(maxheap) * (-1)
                if hash[n] > 0:
                    hash[n] -= 1
                    break
    if cnt == 0: return [INF, INF]  # 뺄 원소가 없는 경우
    min_res, max_res = INF, INF * (-1)
    for i in list(hash.keys()):
        if hash[i] > 0:  # 최대 / 최소값 갱신
            min_res = min(min_res, i)
            max_res = max(max_res, i)
    return [max_res, min_res]


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

for _ in range(t):
    operation = list()
    n = int(sys.stdin.readline())
    for _ in range(n):
        temp = sys.stdin.readline().rstrip()
        operation.append(temp)
    a, b = solution(operation)
    if a != INF and b != INF:
        print(a, b)
    else:
        print("EMPTY")

 

 

풀이

- 프로그래머스의 이중우선순위큐와 동일한 문제다. ( https://school.programmers.co.kr/learn/courses/30/lessons/42628 )

- 풀이는 동일하게 hash, maxheap, minheap을 구현하여 풀이한다. (https://yhah.tistory.com/424)

- 다만 원소의 범위가 -2^32에서 2^32이기 때문에 적당히 큰 수를 지정해야 해당 문제에서 오답이 발생하지 않는다.

 

 

알게된 점

- int(1e9)로 지정해서 풀었더니 93%에서 오답이 발생했었다.

 

 

참고 사이트

-