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

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

 

목차

 

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

1931번: 회의실 배정

Python

 

방법 1 - 메모리 57780KB / 시간 296ms / 코드 길이 237B

 

이 부분에서 핵심은 회의실 배정에 있어 최대가 되도록 하는 방향이다.

핵심 아이디어는 정렬된 list 값들을 기반으로 시작하는 시간과 끝나는 시간에 대한 비교를 잘 진행하는 것이다.

첫 시도때 잘못 생각한 탓에 dfs를 고려했고 이를 통해 2번의 for 문을 사용했으나 다음 코드에서 확인할 수 있듯 짧은 시간들을 앞쪽으로 배치하는 정렬을 진행한다면 한 번의 for문으로도 충분히 해결이 가능하다.

 

Key Sort : 빨리 끝나는 강의 순서(end) -> 수업시간이 빠른 순서(start)

 

list sort시 x[0]에 대해서 후순위로 정렬을 추가한 이유는 해당 항목에 대한 우선순위를 다시 줘야하기 때문

 

가령 예를 들어 0-6까지의 시간까지 마무리한 후 list에는 [8,8],[7,8],[6,8] 과 같은 다음 숫자가 남아있다면 [7,8],[6,8]의 고려 없이 [8,8]만으로 케이스가 끝나므로 최대값을 도출할 수 없습니다.

고로 [6,8],[7,8],[8,8]와 같이 재정렬을 해줘야함.

 

import sys
input=sys.stdin.readline
n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]
l.sort(key=lambda x: (x[1], x[0]))
last = 0
cnt = 0
for s,e in l:
    if s >= last:
        cnt += 1
        last = e
print(cnt)

  

cf) 정렬되는 방법에 따른 결과

# 1) [[0, 6], [1, 4], [2, 13], [3, 5], [3, 6], [3, 8], [5, 7], [5, 9], [6, 10], [8, 11], [8, 12], [12, 14]]
l = [[1,4],[3,5],[3,6],[0,6],[5,7],[3,8],[5,9],[6,10],[8,11],[8,12],[2,13],[12,14]]
l.sort()
print(l)

# 2) [[0, 6], [1, 4], [2, 13], [3, 5], [3, 6], [3, 8], [5, 7], [5, 9], [6, 10], [8, 11], [8, 12], [12, 14]]
l = [[1,4],[3,5],[3,6],[0,6],[5,7],[3,8],[5,9],[6,10],[8,11],[8,12],[2,13],[12,14]]
l.sort(key=lambda x: x[0])
print(l)

# 3) [[1, 4], [3, 5], [3, 6], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]
l = [[1,4],[3,5],[3,6],[0,6],[5,7],[3,8],[5,9],[6,10],[8,11],[8,12],[2,13],[12,14]]
l.sort(key=lambda x: x[1])
print(l)

# 4) [[1, 4], [3, 5], [0, 6], [3, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]
l = [[1,4],[3,5],[3,6],[0,6],[5,7],[3,8],[5,9],[6,10],[8,11],[8,12],[2,13],[12,14]]
l.sort(key=lambda x: (x[1], x[0]))
print(l)