글 읽기 - Python3 두 코드의 차이점이 무엇일까요? (백준 11000 강의실배정)

seongwoo8986 2년 전 1

우선순위 큐를 이용하여 푸는 문제여서 heapq모듈을 써서 해결은 했습니다만, heapq모듈을 사용하지 않고 자체적으로 heap을 구현해보고 싶어서 해봤습니다.

예시에 대해서는 두 코드다 정답이 뜨고 변수도 동일하게 들어가는데 백준에 제출했을 때, 자체적으로 구현한 코드 (2번째 코드) 만 "틀렸습니다"가 뜹니다. 만약 오류가 뜨더라도 시간초과가 떠야하지 않나요?? 이유를 알려주시면 감사하겠습니다. 너무 궁금하네요 ㅠㅠ

# 맞았습니다 코드
import sys
import heapq
N = int(sys.stdin.readline())
Time = []
heap = []
for _ in range(N):
    S,T = map(int,sys.stdin.readline().split())
    Time.append([S,T])
Time = sorted(Time,key=lambda x:(x[0],x[1]))
heapq.heappush(heap,Time[0][1])
for i in range(1,N):
    if Time[i][0] < heap[0]:
        heapq.heappush(heap,Time[i][1])
    else:
        heapq.heappop(heap)
        heapq.heappush(heap,Time[i][1])
print(len(heap))
'''
# 틀렸습니다 코드
import sys
N = int(sys.stdin.readline())
Time = []
heap = []
for _ in range(N):
    S,T = map(int,sys.stdin.readline().split())
    Time.append([S,T])
Time = sorted(Time,key=lambda x:(x[0],x[1]))
heap.append(Time[0][1])
for i in range(1,N):
    if Time[i][0] < heap[0]:
        heap.append(Time[i][1])
    else:
        heap.pop(0)
        heap.append(Time[i][1])
print(len(heap))
'''

seilk 2년 전 1

우선순위 큐 자료구조는 일반 배열과는 다릅니다.

파이썬에서 heapq는 최소힙을 지원하며 모든 루트노드는 자식노드보다 값이 작은 형태의 완전이진트리 형태로 저장합니다.

따라서 일반적인 append, pop을 사용했을때 틀렸습니다가 나오는건 당연합니다.

heap을 구현하고 싶으시면 완전이진트리 자료구조를 만드시고

자료를 업데이트 해줄때마다 단순 append가 아닌 가지는 트리의 값들을 조정하는 log2n의 시간복잡도 과정이 필요합니다.

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

문제

문제

출처

ICPC

Python3 두 코드의 차이점이 무엇일까요? (백준 11000 강의실배정)

seongwoo8986 2년 전 1

seilk 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말