백준 [1931] - 회의실 배정

 

 

문제

1931번: 회의실 배정

 

 

 

[아이디어]

: 회의가 빨리 끝날수록 뒤에 고려해볼 회의들이 많아진다. → 끝시간 기준으로 오름차순 정렬 필요

: 끝시간이 같을 경우에도 고려를 해주어야 한다. → 시작시간 기준으로 오름차순 정렬 필요

  ex) (2,2)와 (1,2)가 있을 때,

        (1,2) (2,2) 순 이면 → 가능한 회의 개수 = 2

        (2,2) (1,2) 순 이면 → 가능한 회의 개수 = 1

 

 

작성한 코드

N = int(input())
time = list()

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

time = sorted(time, key=lambda x: x[0]) #시작시간으로 정렬
time = sorted(time, key=lambda x: x[1]) #끝시간으로 정렬

last = 0 #마지막 시간
count = 0 #회의 개수

for start, end in time: #start는 시작시간, end는 끝시간
  if start >= last: #start과 마지막 회의 시간 비교
    count += 1 #start가 마지막 회의 시간보다 크거나 같으면 1 증가
    last = end #last에 end을 저장

print(count)

- 회의 갯수를 나타내는 N을 입력받고, 시간을 저장할 리스트인 time을 선언해준다.

- N만큼 for문을 돌려서 start, end 변수에 공백을 기준으로 시작시간과 끝시간을 입력받아 time 리스트에 리스트 형으로 저장한다.

- 시작 시간으로 정렬해준 뒤, 끝시간으로 정렬해준다. (우선되는 정렬 기준은 나중에 입력되어야 한다!)

- time만큼 for문을 돌려서 start와 마지막 회의 시간인 last를 비교했을 때,

   start가 마지막 회의 시간보다 크거나 같으면 count를 1증가시키고, end를 마지막 회의 시간에 저장한다.

- 최종적으로 count를 print() 해준다.

 

 

cf.) sorted() 관련 추가 설명

# 예시
array = [('홍길동', 75), ('이순신', 25), ('아무개', 50)]

result = sorted(array, key=lambda x: x[1], reverse=True)

# 결과
[('홍길동', 75), ('아무개', 50), ('이순신', 25)]

- array → 정렬을 적용할 리스트 이름

- key=lambda x: x[1] → 어떤 것을 기준으로 정렬할지

- reverse=True → 내림차순 으로 정렬하고 싶을 때 (기본은 오름차순)

 

 

cf.) 현재 상황은 기준이 여러 개(시작시간 → 끝시간)인 상황인데, 이를 한 번에 처리할 수도 있다고 한다.

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