글 읽기 - 반례가 궁금합니다.

minguu987 2년 전 0

최소힙을 만들고, 수를 한개씩 힙에 push하며, 길이가 N 이상이 됐을 때 pop하여 마지막에 pop한 값을 출력하는 코드를 짜려고 했습니다. 위의 코드는 제가 짜본 코드이고, 아래쪽에 주석 처리한 코드는 정답처리 된 코드입니다.

제가 생각해본 차이점은 힙에 값을 넣고, 크기가 N이상이라면 pop하냐(힙의 최대 크기를 N-1로) 아니면 힙의 크기가 N이상이라면 푸시하고 팝하냐(힙의 최대 크기를 N으로, 마지막에 한번 더 pop) 밖에 없는것 같은데 틀린 이유가 궁금합니다 ㅜㅜ

import heapq
hq = []
N = int(input())
for _ in range(N):
    for i in map(int, input().split()):
        heapq.heappush(hq, i)
        if len(hq)>=N:
            a = heapq.heappop(hq)
print(a)

'''
import heapq
hq = []
N = int(input())
for _ in range(N):
    for i in map(int, input().split()):
        if len(hq)>=N:
            heapq.heappushpop(hq, i)
        else :
            heapq.heappush(hq, i)
print(heapq.heappop(hq))
'''

hyoseok 2년 전 2

반례입니다.

input
2
3 1
4 2

output
2

answer
3

minguu987 2년 전 0

앗 힙크기가 N-1이면 N번째로 큰 수가 먼저 빠질 수 있네요,, 감사합니다!

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

문제

문제

출처

ICPC

반례가 궁금합니다.

minguu987 2년 전 0

hyoseok 2년 전 2

minguu987 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말