[백준] 1931번 : 회의실 배정 (python 파이썬)

 

 

import sys
n = int(sys.stdin.readline())
l = []
if n == 1: # 회의가 1개 열리는 경우 (무조건 1을 출력한다.)
    start, end = map(int, sys.stdin.readline().split(" "))
    print(1)
    
else:
    for i in range(n):
      start, end = map(int, sys.stdin.readline().split(" ")) 
    l2 = sorted(l, key = lambda x: (x[1], x[0])) # 1순위로 끝나는 시간을 기준으로 오름차순, 2순위로 시작하는 시간을 기준으로 내림차순 정렬
      l.append([start, end])
  
    end = l2[0][1]
    ans = 1
    for i in range(1,len(l2)): # 끝나는 시점을 기준으로 가장 가까운 회의를 선택한다. 시작하는 시간이 같은 경우, 끝나는 시간이 가장 빠른 회의를 선택한다.
   
      if l2[i][0] >= end:
        end = l2[i][1]
        ans = ans+1

  
    print(ans)

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

 

1931번: 회의실 배정

 

예제 입력을 보니 끝나는 시점을 기준으로 오름차순으로 정렬이 되어 있었다. 이 지점에서 힌트를 얻은 것 같다.

하지만 시작하는 시간이 같은 경우가 발생할 수 있으며, 시작하는 시간과 끝나는 시간이 같은 경우 또한 존재할 수 있다.

따라서 lambda 함수를 이용하여 1순위로는 끝나는 시간을 기준으로, 2순위로는 시작하는 시간을 기준으로 정렬을 하였다.

 

그러하면

1. 이전 회의 끝나는 시간에서 가장 가깝게 시작하는 회의로 갈 것이다. (1순위로 끝나는 시간으로 정렬을 하였기 때문)

2. 가장 가깝게 시작하는 회의 중 가장 빨리 끝나는 회의가 다음 회의로 선택될 것이다. (2순위로 시작하는 시간으로 정렬을  하였기 때문에, 시작과 끝 시간이 같은 경우로 포함 가능하다.)

 

추가로 위의 회의의 수가 매우 큰 수가 아니므로, 한 번 보았던 회의를 다시 보지 않는 이상 시간 오류는 발생하지 않을 것이라 생각했다.

 

문제는 입력하는 방법과 정렬하는 방법에 따라 시간 오류가 발생할 것이라 생각한다.

 

지금은 lambda를 사용하여 정렬하였지만 더욱 효율적인 방법으로 정렬할 수 있는 방법이 있을 거라 생각하고, 더 찾아봐야겠다.