[BaekJoon] 1931번 : 회의실 배정 (Python)

코딩 1일 1문제! 오늘의 문제는 백준의 회의실 배정입니다.

1931번: 회의실 배정

👨🏻‍💻 문제 풀이

이 문제는 비교적 쉽게 문제를 풀 수 있습니다.

이 힌트를 보고 생각난 방법입니다.

보면 시작시간과 끝시간이 가지런히 정렬 되어있는 것을 볼 수 있습니다.

 

그럼 정렬은 어떤 기준으로 해야하느냐!

 

먼저 문제 속 기준을 보아야합니다.

 

회의실의 개수 == 1개

회의가 시작하면 중간에 중단될 수 없음

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

이때 시작시간과 끝 시간은 같을 수 있음

 

회의실의 개수는 하나이고 회의가 시작하면 중간에 중단될 수 없으므로

빠르게 끝나는 회의 일수록 더 많은 회의가 진행될 수 있으므로 

끝나는 시간이 빠른 순서대로 정렬합니다.

 

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

시작시간이 끝나는 시간과 최대한 가까운 순서대로 있어야

회의 사이 사이의 시간을 최소한으로 줄여서 최대한 많은 회의가 진행될 수 있으므로

두번째 정렬 기준은 시작하는 시간이 빠른 순서입니다.

 

그럼 이렇게 두 가지의 조건을 기준으로 정렬하는 방법은 어떻게 하느냐! 하면

sorted 또는 sort 속의 정렬 옵션 ( key = lambda )  을 활용하면 됩니다.

 

그럼 위의 전제 조건을 활용하여 코드를 작성해보면

먼저 들어오는 input의 형태가 위와 같으므로 

meeting_time = []
for _ in range(int(input())):
	start_time, end_time = map(int, input().split())

	meeting_time.append((start_time, end_time))

meeting_time 리스트를 하나 만들어주고

입력 받는 숫자들을 split()을 활용해 공백을 기준으로 자른 다음 

[문자열, 문자열] 로 만들어진 값을 map을 활용하여 [정수, 정수] 로 바꾸어 준 뒤

meeting_time 리스트에 ( 시작시간, 끝나는 시간 ) 형태로 append 시켜줍니다.

meeting_time = sorted(meeting_time, key=lambda x: (x[1], x[0]))

그 다음 위에서 설정한 정렬 조건대로 정렬합니다.

cnt = 0
before_end_time = 0

for time in meeting_time:
    start_time, end_time = time[0], time[1]
        
    if start_time >= end_time:
        cnt += 1
        before_end_time = end_time

 

정렬한 리스트에서 하나씩 꺼내어 보면서

이전 회의 종료시간과 다른 회의의 시작시간을 비교해서

이전 회의 종료시간 보다 다른 회의의 시작시간이 같거나 클때 하나씩 카운팅합니다.

 

전체 코드는 아래에서!

👨🏻‍💻 코드 ( Solution )

def best_meeting_time(meeting_time):
    cnt = 0
    before_end_time = 0
    meeting_time = sorted(meeting_time, key=lambda x: (x[1], x[0]))
    
    for time in meeting_time:
        start_time, end_time = time[0], time[1]
        
        if start_time >= before_end_time:
            cnt += 1
            
            before_end_time = end_time
            
    return cnt

if __name__ == "__main__":
    meeting_time = []
    for _ in range(int(input())):
        start_time, end_time = map(int, input().split())
        
        meeting_time.append((start_time, end_time))
        
    print(best_meeting_time(meeting_time))

GitHub - SOMJANG/CODINGTEST_PRACTICE: 1일 1문제 since 2020.02.07