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

문제

1931번: 회의실 배정

- 회의실에 최대한 많은 회의를 배정하는 문제이다.

- 배정된 회의는 서로 겹치지 않아야 한다.

- 두 회의의 시작시간과 종료시간은 겹쳐도 된다.

- 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다.

- 시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다.

알고리즘

- 회의 수를 입력받는다.

- 반복문을 통해 회의의 시작시간과 종료시간을 입력받는다.

- 회의 시작시간 기준으로 정렬하고 회의 종료시간 기준으로 다시 정렬한다.

- 반복문을 통해 회의 시작시간과 종료시간을 비교한다.

- 이때, 시작시간이 종료시간보다 크거나 같으면 회의를 배정한다.

코드

n = int(input())
i = []
# 회의시간을 회의 갯수만큼 반복하여 입력받는다.
for _ in range(n):
    i.append(list(map(int,input().split())))

# 회의 시작시간 기준으로 정렬하고 회의 종료시간 기준으로 다시 정렬한다.
i = sorted(i, key=lambda i: i[0])
i = sorted(i, key=lambda i: i[1])
# 비교할 종료시간 초기값
target = 0
# 회의 개수
count = 0
# 시작시간과 종료시간을 
for start, end in i:
    # target보다 시작시간이 크거나 같으면 회의를 배정한다.
    if start >= target:
        # 회의 수 카운트
        count += 1
        # 현재 회의의 종료시간을 target에 넣는다.
        target = end

print(count)

결과

위 코드에서 회의 시간을 두 가지 방법으로 모두 정렬을 한 후에 print(i)를 작성하여 회의시간을 보게 되면 다음 출력 화면과 같이 나오는 것을 확인할 수 있다.

<출력화면>

위 출력 화면을 보게 되면 시작시간 기준으로 정렬하고 종료시간 기준을 다시 정렬했기 때문에 시작시간이 제일 빠르면서도 종료시간이 제일 빠른 회의순서대로 정렬된 것을 확인할 수 있다. 또, 입력을 보게 되면 시작시간이 같은 경우와 종료시간이 같은 경우를 볼 수 있는데 시작시간 기준으로 정렬한 후에 종료시간 기준으로 정렬했기 때문에 종료시간이 같더라도 시작시간이 더 빠른 회의를 먼저 비교할 수 있게 된다. 또 같은 이유로 시작시간이 같더라도 종료시간이 더 빠른 회의를 먼저 비교할 수 있게 된다. 

위 문제를 풀어보고 소프티어의 강의실 배정 문제를 풀면 좋을 것 같다. 문제는 똑같지만 문제의 조건에 따라 푸는 방식이 다르다는 것을 느낄 수 있게 될 것이다. 또 여러 가지 방법으로 이런 유형에 문제를 풀 수 있는 좋은 기회가 될 수 있을 것 같다.

github

junjange/CodingTest