BOJ / Greedy / 회의실 배정 / Python

<1931번>

문제 풀이

'너무 늦게 끝나는 회의를 시작해버리면 다른 회의들을 진행할 수가 없다.'

입력 받은 회의의 시작시간과 끝나는 시간을 저장한 리스트를 두 번 정렬하는 과정이 필요하다.
우선, 회의 시작시간을 기준으로 오름차순 정렬을 한다.

times.sort()

이때 만약 회의의 시작시간(times[~][0])이 같다면 그 다음 인덱스 값인 끝나는 시간(times[~][1])을 기준으로 정렬이 된다.
이후 이번에는 회의 종료시간을 기준으로 정렬을 한다.

times.sort(key=lambda a: a[1])

앞에서 언급했듯 회의 시작시간이 같다면 종료시간을 기준으로 정렬이 되는데 왜 또 다시 종료시간을 기준으로 정렬을 해줘야 할까
문제에서 원하는 답은 가능한 회의의 최대 개수를 출력하는 것이었다.
예를들어 시작시간, 종료시간이 아래와 같은 회의를 입력받았다고 하자.

(0, 15) (1, 4) (4, 6)

시작시간을 기준으로 정렬을 한 번만 한다면 0시 시작 15시 종료인 회의 1개밖에 진행할 수 없다.
종료시간을 기준으로 다시 정렬을 진행하면

(1, 4) (4, 6) (0, 15)

2개의 회의를 진행할 수 있다.

코드

import sys

input = sys.stdin.readline

n = int(input())
times = []

for _ in range(n):
    time = list(map(int, input().split()))
    times.append(time)

times.sort()
times.sort(key=lambda a: a[1])

end = times[0][1]
ans = 1
for i in range(1, len(times)):
    if times[i][0] >= end:
        ans += 1
        end = times[i][1]

print(ans)

---

📝 문제 풀면서

1. 리스트에서 특정 인덱스값으로 정렬하기
   key를 이용한다.

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

# 방법1
times.sort(key = lambda a: a[0])
# 방법2
sorted(times, key = lambda a: a[0])

첫 번째 인덱스값으로 정렬을 원하면 그냥 times.sort()를 해줘도 되는 것 같다.
2차원배열.sort()를 하면 첫 번째 키 값이 동일하면 자동으로 그 다음 키 값에 따라 정렬된다.

2. 리스트에서 특정 값 삭제하기

   • 인덱스로 제거
     • del 리스트[인덱스]
       슬라이싱도 가능하다.
     • 리스트.pop(인덱스)
       매개 변수가 없을 때는 자동으로 -1값이 들어가서 리스트의 맨 마지막 요소를 제거한다.
   • 값으로 제거
     • 리스트.remove(값)
       넘겨준 값을 가지는 원소를 삭제한다.
       해당 값이 여러 개라면 가장 앞에 있는 요소 1개를 삭제한다.
   • 모든 원소 제거
     • 리스트.clear()

3. for문에서 zip
   두 개의 리스트를 for문에서 동시에 돌리고 싶을 때

l1 = [1, 2, 3]
l2 = [4, 5, 6]

for n1, n2 in zip(l1, l2):
	print(n1, n2)
>>>
1 4
2 5
3 6

처음에는 문제를 너무 단순하게 생각했다.
회의의 최대 개수를 출력해야 한다는 것에 대해 깊게 생각하지 않았다.