[백준알고리즘] 1931번: 회의실배정 -Python

[백준알고리즘] 1931번: 회의실배정 -Python

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

1931번: 회의실배정

아랫부분에 새로 푼 방식의 풀이도 추가했다.

 

이번 문제도 그리디 알고리즘을 이용하는 문제이다.

시작시간과 끝나는 시간이 주어질 때 회의실을 이용할 수 있는 최대  횟수를 찾는 문제이다.

 

 

여기서는 문제에 써있는 "단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다." 이 부분이 중요하다.

 

즉 회의의 시작시간과 끝나는 시간도 같을 수 있다는 것은

2

3 3

3 3

의 input이 주어져도 output은 2가 나와야 한다는 것이다.

 

 

주어진 시작시간과 끝나는 시간들을 이용해서 가장 많은 회의의 수를 알기 위해서는 빨리 끝나는 회의 순서대로 정렬을 해야 한다. 이유는 간단하다. 빨리 끝날수록 뒤에서 고려해볼 회의가 많기 때문이다. 빨리 시작하는 순서대로 정렬을 우선 한다면, 오히려 늦게 끝날 수 있기 때문이다.

 

간단한 예를 들자면

4

0 10

3 4

2 3

1 2

가 있을 때 시작 순서대로하면 (0 10)으로 1번의 회의가 가능하지만, 끝나는 시간으로 정렬을 한다면 (1 2) (2 3) (3 4) 총 3번의 회의가 가능해진다.

 

 

그리고 한가지 더 고려해야 하는 점이 있는데, 끝나는 시간이 같을 경우이다.

끝나는 시간이 같다면 빨리 시작하는 순서대로 정렬이 되어야 한다.

예를 들자면

2

2 2

1 2

의 경우 이 상태로 한다면 (2 2)가 되고 (1 2)는 (2 2)의 끝나는 시간보다 시작시간이 일찍이기 때문에 무시되어 1번의 회의가 진행된다고 나온다. 하지만 정렬을 통해 (1 2)가 먼저 선택되면 (2 2)도 선택이 가능해지기 때문에 가능한 회의는 2번으로 결정된다.

 

 

그렇기 때문에 정렬을 1. 끝나는 시간의 오름차순 2. 시작하는 시간의 오름차순으로 해주어야 한다.

 

위의 정렬을 해주기 위해서는 파이썬의 sort를 이용해서 2가지 정도의 가능한 풀이가 있는데

 

한 가지는 전체를 시작시간의 오름차순으로 정렬을 한 뒤, 정렬된 리스트를 다시 끝나는 시간으로 오름차순 정렬해주는 것이다. 이미 시작시간이 오름차순으로 정렬된 상태이기 때문에 끝나는 시간으로 오름차순을 해주어도 자연히 끝나는 시간이 같을 때에는 시작시간의 오름차순으로 정렬이 되어있다.

 

다른 한가지는 한 번에 정렬을 해주는 것이다. 원래 key로 인자 하나를 주는 것은 알고 있었지만 이번 문제를 풀면서 혹시 가능할 것 같아서 찾아보니 key에 튜플로 여러 인자를 주면 해당 안자의 순서대로 정렬을 해준다고 알게 되었다.

 

전자는 그냥 sort를 두 번 사용하면 되기 때문에 굳이 적지 않을 것이고 후자는 밑의 풀이 코딩에 나와있기 때문에 따로 적지 않을 것이다.

 

import sys

N = int(sys.stdin.readline())

time = [[0]*2 for _ in range(N)]
for i in range(N):
    s, e = map(int, sys.stdin.readline().split())
    time[i][0] = s
    time[i][1] = e

time.sort(key = lambda x: (x[1], x[0]))

cnt = 1
end_time = time[0][1]
for i in range(1, N):
    if time[i][0] >= end_time:
        cnt += 1
        end_time = time[i][1]

print(cnt)

 

20200411

오랜만에 풀어봤는데 풀다 보니 전깃줄 문제와 비슷하게 느껴졌다.

물론 다른 점도 많다. 가장 큰 점은 시작 시각이 이전의 회의 종료시각보다 늦어져야 한다는 것이다.

코드는 아래와 같이 작성했다.

 

개념자체는 이전에 풀었던 식과 크게 다르지 않는데 불필요한 부분을 없앴다.

하지만 그만큼 시간은 늘어났다.

n = int(input())
time = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x:(x[1], x[0]))
ans = end = 0
for s, e in time:
    if s >= end:
        ans += 1
        end = e
print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다