(Python) 백준 1931번: 회의실 배정

출처 : https://www.acmicpc.net/problem/1931

1931번: 회의실배정

알고리즘 분류:

• 그리디 알고리즘

---

시간이 들쭉날쭉 나오는데 그 원인을 알고싶어서 시작했다.

입력을 어떻게 받아야 시간이 단축되는걸까?

import sys
 
N = int(input())
 
meeting = []
for i in range(N):
    start,end = map(int,sys.stdin.readline().split())
    meeting.append((start,end))
    
meeting = sorted(meeting, key=lambda time : time[0])
meeting = sorted(meeting, key=lambda time : time[1])
 
select_meeting = []
select_meeting.append(meeting[0])
next_start = meeting[0][1]
for i in range(1,len(meeting)):
    if(meeting[i][0] >= next_start):
        next_start = meeting[i][1]
        select_meeting.append(meeting[i])
        
print(len(select_meeting))

import sys
input = sys.stdin.readline
 
N = int(input())
 
meeting = []
for i in range(N):
    meeting.append([int(j) for j in input().split()])
    
meeting = sorted(meeting, key=lambda time : time[0])
meeting = sorted(meeting, key=lambda time : time[1])
 
select_meeting = []
select_meeting.append(meeting[0])
next_start = meeting[0][1]
for i in range(1,len(meeting)):
    if(meeting[i][0] >= next_start):
        next_start = meeting[i][1]
        select_meeting.append(meeting[i])
        
print(len(select_meeting))
 

아직까지는 크게 차이가 없다.

 

 

 

 

리스트와 map을 결합해서 한줄에 해결하려고 하면 시간이 오래걸린다는 소리가 있어서 해봤는데

이것도 별 차이가 없었다.

import sys
input = sys.stdin.readline
 
N = int(input())
 
meeting = [list(map(int, input().split())) for _ in range(N)]
    
meeting = sorted(meeting, key=lambda time : time[0])
meeting = sorted(meeting, key=lambda time : time[1])
 
select_meeting = []
select_meeting.append(meeting[0])
next_start = meeting[0][1]
for i in range(1,len(meeting)):
    if(meeting[i][0] >= next_start):
        next_start = meeting[i][1]
        select_meeting.append(meeting[i])
        
print(len(select_meeting))
 

 

 

 

 

import sys

input = sys.stdin.readline

이 부분을 없애주고 input()으로만 입력받게 해봤다.

N = int(input())
 
meeting = []
for i in range(N):
    start,end = map(int,input().split())
    meeting.append((start,end))
    
meeting = sorted(meeting, key=lambda time : time[0])
meeting = sorted(meeting, key=lambda time : time[1])
 
select_meeting = []
select_meeting.append(meeting[0])
next_start = meeting[0][1]
for i in range(1,len(meeting)):
    if(meeting[i][0] >= next_start):
        next_start = meeting[i][1]
        select_meeting.append(meeting[i])
        
print(len(select_meeting))
 

시간 차이 무엇....?

상황에 따라서는 input()으로만 입력값을 받는게 더 빠른 경우도 많았는데

이번 문제는 sys.stdin.readline()으로 입력받는게 훨씬 빨랐다.

값을 입력받을때 상황에 따라서 더 좋은게 확실히 갈리는 것 같다.

 

 

 

 

사실 위의 코드는 7달전에 풀었던것이고

아래 코드가 이번에 새로 풀어본건데, 새로 풀고나서 시간이 너무 많이 나오길래 옛날 코드를 가져와서 한번 비교해봤던 것이다.

이번에 풀었던 코드가 input()으로만 입력을 받았기 때문에 시간이 오래 나온걸지도 모르겠다.

sys.stdin.readline을 추가시켜보겠다.

import sys
input = sys.stdin.readline
 
N = int(input())
array = [list(map(int, input().split())) for _ in range(N)]
 
array.sort()
 
anv = [[array[0][0], array[0][1]]]
for node in array[1:]:
    ## 마지막 회의의 끝시간과 새로운 회의의 끝시간 비교
    ## 마지막 회의보다 더 빨리 끝나면 교체
    if node[1] < anv[-1][1]:
        anv.pop()
        anv.append(node)
    ## 마지막 회의보다 늦게(혹은 동시에) 끝나는 경우
    else:
        ## 마지막회의의 끝과 새로운 회의의 시작시간 비교
        if anv[-1][1] <= node[0]:
            anv.append(node)
print(len(anv))

4276ms -> 344ms로 단축됐다.