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

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

 

1931번: 회의실 배정

---

문제

---

풀이

0.방향성 생각

회의가 끝나야 다음 순번이 들어온다.
끝나는 시간 순으로 정렬한 후 다음 순번은 시작시간이 가장 빠른 것을 찾으면 된다.

[[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]

테스트 케이스를 정렬하면 이런식으로 된다.
 

1. 전체코드

n = int(input())
arr = []
for i in range(n):
    arr.append(list(map(int,input().split())))

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

answer = [arr[0]]
for i in arr[1:] :
    if i[0] >= answer[-1][-1] :
        answer.append(i)
print(len(answer))

테스트 케이스에서 [1,4]에서 시작한다. 시작시간이 [1,4]보다 작은 경우에는 회의실 사용중이므로 [3,5],[0,6]은 패스한다.
[5,7]은 회의실이 비어있을 때 가장 먼저 사용하고 가장 먼저 끝나는 케이스이다. arr에 추가한다.
 
for i in arr : 이런식으로 돌리면 n n같은 이상한 입력이 들어오면 오답이 발생한다.
상식적으로 회의 시작시간, 끝시간이 똑같은 케이스는 뺐으면 좋겠다.
 
 

---

 

코멘트

코테에서 쉬운? 문제로 나올법한 문제. 정렬한다는 생각만 해주면 판자채우기, 징검다리 유지보수? 문제랑 비슷해서 쉽게 풀었다.
key에 람다함수 넣어서 n번째 요소로 정렬하는거 몰라도 입력 받을 때 순서를 바꿔서 리스트에 저장하거나 충분히 다른 방법은 많다.
그리디인건 인지 못했음