[BOJ] 회의실 배정(1931) - PYTHON

N개의 회의 사용시간(시작시간, 끝나는 시간)이 들어올 때 회의를 할 수 있는 가장 많은 경우의 수를 찾아서 그 값을 반환하는 문제다. N은 최대 10만이며, (시작시간, 끝나는 시간)은 INT최댓값으로 들어온다.

이때 시작시간, 끝나는 시간이 같을 수 있으며, 회의가 끝나는 시간에 다른 회의가 시작될 수 있다.
(일반적 논리와는 맞지 않음에 주의한다.)

시간복잡도: O(NlogN)

1931번: 회의실 배정

 

---

풀이 방법

가능한 많은 회의를 만들어야 하므로, 우선 입력값을 차례대로 비교해보기 위해 들어온 (회의 시작시간, 회의 끝나는 시간)을 오름차순으로 정렬한 배열을 생성한다. 이렇게 하면 시작시간이 빠른 값이 앞에 오고, 시작시간이 같다면 끝나는 시간이 빠른 값이 앞에 오게 된다.

이후 리스트에서 값을 차례대로 확인하며 해당 회의를 진행할 수 있는지 판별해야 한다. 이때 판별 방법은 앞에서 진행한 회의의 끝나는 시간이 판별할 회의의 시작시간보다 크거나 같은 지 확인하면 된다. (ex 마지막으로 진행하려고 한 회의가 (1,4)이고 현재 판별할 회의가 (5,6)이면 현재 회의를 진행할 수 있다.)

또한 판별할 회의의 시작시간이 진행하려고 했던 회의 시작시간보다 늦지만, 끝나는 시간이 빠르다면, 이 회의는 현재 회의로 대체하는 것이 이득이므로 대체시킨다. (ex 마지막으로 진행하려고 한 회의가 (2,5)이고, 현재 판별할 회의가 (3,4)라면, 앞 회의의 진행을 취소하고 현재 회의를 진행시키는 것이 이득이다.)

따라서 변수를 하나 선언해 마지막으로 진행하려고 했던 회의의 끝나는 시간을 저장한 뒤에, 판별할 회의의 시작시간이 저장한 변수보다 크거나 같다면 정답 값+1을 하고 변숫값을  현재 회의의 끝나는 시간으로 업데이트한다.
또 변숫값(마지막 회의의 끝나는 시간)이 현재 회의의 시작시간보다 크지만 끝나는 시간보다 작다면 변숫값을 현재 회의 의의 끝나는 시간으로 업데이트한다.  

---

코드

import sys
 
input = sys.stdin.readline
 
N = int(input())
arr = []
for _ in range(N):
    val = tuple(map(int, input().split()))
    arr.append(val)
arr.sort()
answer = 0
maxval = -1
 
for a, b in arr:
    if a >= maxval:
        answer += 1
        maxval = b
    elif maxval > b:
        maxval = b
 
print(answer)
 

주석 추가

import sys
 
input = sys.stdin.readline
 
N = int(input())
arr = []  # 입력값을 저장할 배열
for _ in range(N):
    val = tuple(map(int, input().split()))  # 입력값(회의시작시간, 끝나는시간)을 tuple형태로 저장
    arr.append(val)
arr.sort()  # 입력 값을 오름차순으로 정렬
answer = 0
maxval = -1  # 현재까지 진행할 수 있는 마지막 회의의 끝나는 시간
 
for a, b in arr:  # a: 회의 시작시간 b: 회의 끝나는 시간
    if a >= maxval:  # 앞선 마지막 회의의 끝나는 시간이 현재 회의의 시작 시간보다 작거나 같다면
        answer += 1  # 정답 +1
        maxval = b  # 마지막 회의 끝나는 시간 업데이트
    elif maxval > b:  # 앞선 마지막 회의의 끝나는 시간이 현재 회의의 끝나는 시간보다 크다면
        maxval = b  # 마지막 회의의 끝나는 시간을 현재 회의 끝나는 시간으로 대체 (앞선 마지막 회의 대신 현재 회의를 진행)
 
print(answer)
 

 

input이 최대 10만 줄 들어오므로 sys모듈을 통해 입력시간을 단축했다.

---

채점 결과

앞선 시도들에서는, 회의 끝나는 시간에 다른 회의가 시작할 수 있다는 조건을 놓쳐서 틀렸다.