글 읽기 - 파이썬 시간초과 도와주세요 ㅠㅠㅠ

kk5068 2년 전 0

원래 while 안에 for 문도 있었는데 수정해서 없앴는데도 시간초과가 나네요 ㅠㅠㅠ

import sys
input = sys.stdin.readline
N= int(input())
time = []
cnt = 0
i = 0
for _  in range(N):
  a,b = map(int,input().split())
  time.append([a,b])

time.sort() # 시작시간 순으로 정렬, 시작시간이 같으면 끝나는 시간 정렬

A = time[0]
time.remove(A)
while(1):

  if len(time) == 0: # 비교 대상이 없을경우 종료
    break

  if A[1] <= time[i][0]: # 다음 회의 시작시간이 같거나 클때

    if A==time[i]: # 회의 시작시간이 같을때
      cnt+=1
      A = time[0] # 회의 시간 간격이 같을때

      if len(time)==1: # 마지막 남은 시간일때
        cnt+=1
      time.remove(time[i])
      if i>=len(time):
        i=0
      #break
      continue

    A = time[i]
    time.remove(A)
    if i>=len(time):
      i=0
    #break
    continue
    
  elif A[1]>time[len(time)-1][0]: # 다음회의 시작시간이 끝나는 시간보다 작을때
    cnt+=1
    A = time[0]
    
    if len(time)==1: # 마지막 남은 시간일때
      cnt+=1
    time.remove(A)
    if i>=len(time):
      i=0
    #break
    continue
  else:
    i+=1
    # if i>len(time):
    #   i=0


print(cnt)

leejm 2년 전 0

리스트의 remove 메소드를 사용해서 그런거 같아요.

remove를 쓰면 배열의 마지막 원소부터 첫 번째 원소 쪽으로 조회하다가 원하는 원소를 만나야 삭제가 되기 때문에 위 방법 대로 하면 항상 배열의 길이만큼 조회를 하고 삭제를 하게 되서 굉장히 느려집니다.

remove를 할 필요 없이 배열의 처음부터 인덱스를 통해 조회하시면 훨씬 빠르실겁니다.

kk5068 2년 전 0

이제보니 제가 문제를 잘못이해하고 있었네요 ㅠㅠㅠ 저는 최대로 사용가능한 회의실의 개수를 구하는문제인줄 알았습니다 ...ㅎㅎㅎㅎㅎ

감사합니다 해결했어요!

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

문제

문제

출처

ICPC

파이썬 시간초과 도와주세요 ㅠㅠㅠ

kk5068 2년 전 0

leejm 2년 전 0

kk5068 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말