글 읽기 - (파이썬) 시간복잡도는 맞춘듯한데 4프로에서 틀렸다고 나옵니다.

dlgusrb3456 1년 전 0

코드에 대한 자세한 설명은 코드에 주석으로 설명해두었습니다.

구글 검색을 통해 확인해도 알고리즘이 틀리지 않은것 같은데 4프로에서 틀렸다고 나와 질문 올립니다. (시간 초과는 발생하지 않습니다)

반례 혹은 알고리즘적으로 틀린 부분이 있을까요?

import sys
from collections import deque
from queue import PriorityQueue
import heapq

nCount = int(input())
nList = []

for _ in range(nCount):
    nums = list(sys.stdin.readline().split())
    nList.append(nums)


nList = sorted(nList,key = lambda x :(x[0],x[1])) #시작시간 기준 정렬, 시작 시간이 같으면 끝나는 시간 기준 정렬
dList = deque(nList) #정렬한 리스트 deque화

cList = []

heapq.heappush(cList,dList.popleft()[1]) #시작시간이 가장 빠른 강의의 종료시간을 heapq에 넣어줌


while dList: #모든 강의를 처리할때까지
    cTime = dList.popleft()    #강의 하나 가져오기

    earlyEndTime = heapq.heappop(cList) #가장 수업이 빨리 끝나는 강의실
    if cTime[0] < earlyEndTime:         #가장 빨리 수업이 끝나는 강의실과 비교해서 가져온 강의의 시작시간이
                                        #더 이르면 25에서 빼온 강의실 다시 추가
        heapq.heappush(cList, earlyEndTime)

    heapq.heappush(cList, cTime[1])    #더 이르지 않으면 해당 강의실의 끝나는 시간을 새로 가져온 강의의 끝나는 시간으로 정정


print(len(cList)) #강의실의 갯수만큼 존재하는 heapq의 길이

dlgusrb3456 1년 전 0

입력에서 생긴 문제였네요

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

문제

문제

출처

ICPC

(파이썬) 시간복잡도는 맞춘듯한데 4프로에서 틀렸다고 나옵니다.

dlgusrb3456 1년 전 0

dlgusrb3456 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말