백준 1931 [회의실 배정]

문제링크: https://www.acmicpc.net/problem/1931

 

♣ 문제정리

• 시작시간, 끝나는 시간을 가진 회의들이 있을 때, 회의 수의 최대 개수를 출력하는 문제.
• 회의가 겹칠 수 없다
• 회의가 끝나는 동시에 다음 회의가 시작될 수 있다

 

♣ 코드 작성 전 생각할 거리

입력받은 회의들을 시작시간을 기준으로 정렬을 먼저 하기. (회의가 끝났을 때 다음 회의의 시작하는 시간을 바탕으로 계산해야 될 것 같음)

 

첫 회의의 시작시간은 빠를 수록 좋을 줄 알았지만 duration이 길면 이것도 명제가 될 수 없다

(이전 회의 끝나는 시간 <= 다음회의의 시작시간) 의 순서로 하되, 다음 회의의 시작시간이 같은 것들이 여러개라면?

 

start, duration, end 시간을 다 고려를 해야 할 것 같다.

 

===> greedy 기법으로 생각해 본다면, 여러 선택지들이나 두개의 선택지가 있을 때, 어떤 하나를 선택했을 때 더 빨리 끝나는 회의를 우선적으로 선택하면 되지 않을까?

 

한 가지 더, 끝나는 시간이 같을 경우는? 

빨리 시작하는 회의를 우선적으로 선택해야 한다.

2

2 2

1 2

위 경우 (1 2)를 선택한다면 (2 2)도 선택이 가능해지므로 가능한 회의는 2번으로 결정되지만

(2 2)를 선택한다면 가능한 회의는 1번만으로 결정된다.

 

1. 끝나는 시간을 기준으로 오름차순 정렬

2. 끝나는 시간이 같다면 시작하는 시간이 적은 순으로 오름차순 정렬

 

 

♣ 코드 작성

import sys

input = sys.stdin.readline
n = int(input())

meetings = []
for i in range(n):
    each = list(map(int, input().strip().split(" ")))
    meetings.append(each)

# 끝나는 시간을 기준으로 오름차순 정렬 후 시작시간을 기준으로 오름차순 정렬을 함
meetings = sorted(meetings, key=lambda item: (item[1], item[0])) 

end = meetings[0][1]
cnt = 1

for i in range(1, n):
    if end <= meetings[i][0]: # 다음회의 시작시간이 현재 끝난 시간보다 크거나 같은 것만
        cnt += 1
        end = meetings[i][1]

print(cnt)

전처리를 해주는 과정을 잘 이해하고 코드를 짠다면 뭔가 정말.. 소위 computational thinking으로 쉽게 풀 수 있게 되는 것 같다. 그렇지 않았다면 코드가 복잡해졌을 것 같다.

 

아래 코드는 input() 함수를 사용한 시간이고, 위 코드는 sys.stdin.readline() 을 사용한 시간이다.

 

반복문으로 여러 줄 입력받는 상황에서는 !반드시! 입력은 sys.stdin.readline() 으로 사용해야 겠다!

다만, 한 줄 단위로 입력받기 때문에 개행문자만 제거해주는 strip() 함수만 잘 사용해주자.