글 읽기 - 성공한 C++ 코드를 python 코드로 변경하면 틀렸습니다! 무엇이 문제일까요?

zkfthfl 2년 전 0

https://kau-algorithm.tistory....

위 블로그 글의 C++코드를 참고하여 파이썬 코드를 작성하였고
게시판의 모든 반례를 테스트 해본 결과 잘 돌아감을 확인했습니다!

알고리즘을 요약하자면...

최소, 최대 힙(음수로 저장)을 만들고

각각의 힙은 동일한 입력값을 저장하고 있다는 점을 사용하여

입력된 숫자의 개수가 저장된 딕셔너리를 만들고

최대값, 최소값을 각각의 최대, 최소 힙에서 뺄때 딕셔너리에 저장된 숫자의 개수가 0 이라면

이미 그 값은 반대편 힙에서 빠져나간 경우이므로 pop 수행하여 버린 후 다음 값 확인

자세한 내용은 블로그에 잘 정리되어 있습니다.

어느 부분에서 실수를 했을까요?
무엇이 문제일까요... ㅠㅠ

import sys
import heapq
from collections import defaultdict

input = sys.stdin.readline

def solution(operations):
    answer = []
    num_dict = defaultdict(int)
    min_heap = []
    max_heap = []
    for o in range(operations):
        oper, num = input().split()
        num = int(num)
        if oper == 'I':
            num_dict[num] += 1
            heapq.heappush(min_heap, num)
            heapq.heappush(max_heap, -num)
        else:
            if num == 1:
                while(max_heap):
                    max_num = -heapq.heappop(max_heap)
                    if num_dict[max_num] != 0:
                        num_dict[max_num] -= 1
                        break
            else:
                while(min_heap):
                    min_num = heapq.heappop(min_heap)
                    if num_dict[min_num] != 0:
                        num_dict[min_num] -= 1
                        break
    
    while(max_heap and num_dict[-max_heap[0]] == 0): heapq.heappop(max_heap)
    while(min_heap and num_dict[min_heap[0]] == 0): heapq.heappop(min_heap)

    if not max_heap: print('EMPTY')
    else: print(-max_heap[0], min_heap[0])

T = int(input())
print(T)
for _ in range(T):
    k = int(input())
    solution(k)

zkfthfl 2년 전 0

하.................................................

T = int(input())

print(T) <---------------------------------- (삭제)

for _ in range(T):

k = int(input())

solution(k)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

성공한 C++ 코드를 python 코드로 변경하면 틀렸습니다! 무엇이 문제일까요?

zkfthfl 2년 전 0

zkfthfl 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말