[백준 파이썬] # 1931 회의실 배정

Siver II

# 1931 회의실 배정

그리디 알고리즘 유형

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

1931번: 회의실 배정

 

풀이

N = int(input())
time = []


for i in range(N):
    start, end = map(int, input().split())
    time.append([start, end])


time = sorted(time, key = lambda a : a[0]) # start 기준으로 오름차순 정렬   
time = sorted(time, key = lambda a : a[1]) # end 기준으로 오름차순 정렬

## 오름차순 정렬 시 시간복잡도 : O(NlogN)
## 2차원 요소를 기준으로 정렬할 때 sorted(list, key = lambda a:a[n]) 사용

last_end = 0
cnt = 0

for start, end in time:
    if start >= last_end:
        cnt += 1
        last_end = end

print(cnt)

 

• end와 start를 기준으로 정렬하는 아이디어를 떠올려야 한다
  • 먼저 끝날 수록, 이후 시간에 예약할 수 있는 여유가 많아진다 : end 기준 정렬
  • 끝나는 시각이 같을 때, 발생할 수 있는 예외에 대해서 고려해야 한다: start 기준 정렬
  • ex) 입력값이 n = 2, start, end = [(2 2), (1 2)] 일 때​
    • end, start 기준 정렬했을 때 time = [(1 2), (2 2)] : cnt = 2
    • ​end 기준 정렬만 이용한다면 time = [(2 2), (1 2)] : cnt = 1

 

• 우선되는 기준 정렬을 나중에 입력해야 한다 ※ 혼동 주의
  • a[0] & a[1] 정렬 != a[1] & a[0]
    • a[1] & a[0] : a[0]을 우선 기준으로 정렬되고, a[1]이 차순 기준으로 정렬된다
    • a[0] & a[1] : a[1]을 우선 기준으로 정렬되고, a[0]이 차순 기준으로 정렬된다

 

• 2차원 요소를 기준으로 정렬할 때 sorted(list, key = lambda a : a[n])을 사용할 수 있다
  • lambda로 정의하는 변수(a)는 자유롭게 바꿔도 됨
  • 기준을 여러 개 적용할 때 sorted(list, key = lambda a : (a[m], a[n]))과 같이 사용할 수 있다

 

N = int(input())
time = []


for i in range(N):
    start, end = map(int, input().split())
    time.append([start, end])

time = sorted(time, key = lambda a : (a[0], a[1]))  # point  

last_end = 0
cnt = 0

for start, end in time:
    if start >= last_end:
        cnt += 1
        last_end = end

print(cnt)

 

 

참고하면 좋을 영상 및 사이트

• https://youtu.be/7noZLdfHIMQ

신찬수 교수님 영상

• https://suri78.tistory.com/26

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