[백준 1931 : PYTHON] 회의실 배정

문제 풀기 : 1931번

1931번: 회의실배정

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만든다.

각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있다.

각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾는다.

단, 회의는 한번 시작하면 중간에 중단될 수 없다.

한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

회의의 시작시간과 끝나는 시간이 같을 수도 있다. (이 경우에는 시작하자마자 끝나는 것으로 생각한다.)

문제풀이

최적의 해를 구하는 그리디 문제이다.

회의실을 최대로 사용하려면 회의가 끝나는 시간이 짧은 순으로 회의를 진행하면 된다.

회의가 끝나는 시간순으로 오름차순 정렬을 한 뒤 회의가 시작되는 시간순으로 오름차순 정렬을 해준다.

그런 뒤 회의 끝나는 시간과 다음 회의의 회의 시작시간을 비교한다.

처음 코드 작성 시 데이터 정렬을 할 때 sorted 함수를 사용했다가 틀렸다는 채점 결과를 얻었다.

원본 값이 바뀌지 않아서 생긴 문제점으로 원본 데이터를 바꾸고자 한다면 sort 함수를 써야한다.

코드 TIP

sort : 리스트명.sort( ) 형식으로 "리스트형의 메소드"이며 리스트 원본값을 직접 수정한다.

sorted : sorted( 리스트명 ) 형식으로 "내장 함수"이며 리스트 원본 값은 그대로이고 정렬 값을 반환한다.

전체코드

# n : 회의 개수, data : 각 회의의 시작시간과 끝나는 시간을 담은 리스트
n = int(input())
data = []

for i in range(n):
    data.append(list(map(int, input().split())))

# 끝나는 시간을 우선순위로 정렬
data.sort(key=lambda data: (data[1], data[0]))


result = 0
tmp = 0
for i in range(n):
    # 끝나는 시간과 그 다음 회의의 시작시간 비교
    if tmp <= data[i][0]:
        result += 1
        tmp = data[i][1] 
print(result)