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

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1 

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 1 

4

힌트

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

---

 문제 해결 과정

 

해당 문제는 그리디 알고리즘 문제, 백준 실버 1 문제이다.

 

이 문제는 시작 시간, 마치는 시간을 리스트로 만들어, 정렬한 뒤 해결해야 하는 문제이다.

 

일단 나는 처음에 시작 시간과 마치는 시간의 리스트를 따로 만들어 입력을 하려고 했다.

그렇게 하려다 보니 [1, 4], [3, 5] ... 이렇게 담지 못하고, 제각각 담겨서 비교가 불가능 하다고 생각이 들었다.

 

그래서 딕셔너리 자료형으로 담을까 하고 생각을 했다.

지금 생각해보면 딕셔너리 자료형으로도 문제가 해결될 것 같지만, 나는 [(1, 4), (3, 5)...]식으로 파이썬에서 담을 수 있다는 사실을 모르고 있었다.

 

결국은 1 4, 3 5, 0 6을 리스트에다가 담았다.

 

N = int(input())

time = list()
for _ in range(N) :
    start, end = map(int, input().split())
    time.append([start,end])
    
''' 처음에는 다음과 같이 작성하려고 했다
start, end = map(int, input().split())
for _ in range(N) :
	start.append(start)
    end.append(end)

이렇게 하니까 담기지도 않을뿐만 아니라, 아까 말했던 문제가 발생했다. '''

 

그 다음은 이제 정렬이다.

 

어떻게 정렬을 해야할까?

정렬을 무작정 오름차순, 내림차순으로 할 수도 없는 것이다.

(0, 11), (3, 5), (6, 9) 가 있다고 가정해보자.

시작 시간은 (0, 11)으로 가장 빠르지만,

(3, 5), (6, 9)의 두 가지 경우가 나오는 것이 답이다.

 

그러면 시작 시간 오름차순으로 먼저 정렬을 하고, 그 다음에 마치는 시간을 오름차순으로 정렬을 하면 된다고 생각했다.

 

time = sorted(time, key=lambda a : a[0]) # 시작 시간 기준으로 오름차순 정렬
time = sorted(time, key=lambda a : a[1]) # 마치는 시간 기준으로 내림차순 정렬

count = 0
last = 0

''' 예제 입력 1 기준으로 
[[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]
으로 정렬된다. '''

''' 위 방법이 오름차순으로 정렬하는 방법이다. 알아두도록 하자. '''

 

그러면 이제 첫 번째 리스트 인덱스부터 시작 시간과 마치는 시간을 비교하여 count 하면 된다.

 

첫 번째 인덱스의 마치는 시간 보다 두 번째(다음) 인덱스의 시작하는 시간이 같거나 크면 count 하고 마치는 시간도 두 번째(다음) 인덱스의 마치는 시간으로 업데이트 한다.

 

count = 0
last = 0

for i, j in time :
    if i>=last :
        count += 1
        last = j

print(count)

 

따라서, 모든 코드는 다음과 같다.

 

N = int(input())

time = list()
for _ in range(N) :
    start, end = map(int, input().split())
    time.append([start,end])
    
time = sorted(time, key=lambda a : a[0])
time = sorted(time, key=lambda a : a[1])

count = 0
last = 0

for i, j in time :
    if i>=last :
        count += 1
        last = j

print(count)

 

문제

 

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

1931번: 회의실 배정