백준 1931. 회의실 배정 (Python/파이썬) (그리드 알고리즘, 다중 리스트 정렬)

dding_ji·2021년 9월 15일
1
post-thumbnail

🔎 6588번. 문제 보기
https://www.acmicpc.net/problem/1931

💡 문제 풀기 전

그리디 알고리즘을 활용해야 하는 문제!
코딩테스트 관련 책에서 그리디 알고리즘 예제를 몇 문제 풀어봤는데
너무 쉬운 난이도의 문제들이라 얕잡아봤다가.. 백준에서 큰 코 다쳤다😥
처음에 접근하기까지 아이디어를 떠올리는데 고민을 많이 했다.
근데 막상 문제 풀이를 마치고 나니 그리 어렵지 않았던..? 문제랄까!

처음에 핵심 키를 1-2개만 잘 갖고 출발하면 누구나 무난하게 풀 수 있을 것이다 :)

📋 코드 보기

from sys import stdin

N = int(stdin.readline())
time = sorted([list(map(int, stdin.readline().split())) for i in range(N)])
time = sorted(time, key = lambda time : time[1])

start = 0
cnt = 0

for i in range(len(time)):
    if time[i][0] >= start:
        start = time[i][1]
        cnt += 1

print(cnt)

🥕 코드 풀이 및 관련 개념

1. 문제 풀이 아이디어
고려해야 할 요소는 총 2가지다.

'시작 시간' 그리고 '종료 시간'

백준에서 주어진 예제 입력1을 기준으로 생각을 해보자.

11   #회의의 최대 개수
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

여러 회의 시간이 주어졌지만 가장 먼저 해야 할 일은 '시작 시간'이 빠른 순서대로 정렬을 해야하는 것이다.

11   #회의의 최대 개수
0 6
1 4
2 13
3 5
3 8
5 7
5 9
6 10
8 11
8 12
12 14

정렬을 하고 나면 '시작 시간'이 빠르다고 해서 덜컥 경우의 수에 넣어버리면 안 된다는 것을 알 수 있다. (0, 6)은 시작 시간이 가장 빠르지만 (0, 6) 대신에 (1, 4)를 선택하는 것이 더 많은 회의 개수를 가져올 수 있기 때문이다.

결국 우리는 '종료 시간'도 함께 고려해야 한다는 것을 알 수 있다. 그렇다면 여기서 '종료 시간'을 기준으로 정렬을 1번 더 해준다면 어떻게 될까?

11   #회의의 최대 개수
1 4
3 5
0 6
3 8
5 7
5 9
6 10
8 11
8 12
2 13
12 14

이제 맨 앞에 시작 시간과 종료 시간이 가장 빠른 회의가 왔다.
다음으로 첫 회의의 종료 시간 '4'를 기준으로 (3, 5), (0, 6), (3, 8)을 모두 지나
(5, 7) 회의를 선택할 수 있게 되는데,

지금부터 같은 패턴이 반복된다고 생각하면 된다.
(5, 7) 회의의 종료 시간 '7'을 기준으로 다시 (5, 9), (6, 10)을 지나
(8, 11) 회의를 선택

(8, 11) 회의의 종료 시간 '11'을 기준으로 (8, 12), (2, 13)을 지나
(12, 14) 회의를 선택

결론적으로 가장 효율적인 방법을 선택했을 때 가능한 회의는
(1, 4), (5, 7), (8, 11), (12, 14)
총 4가지다.

문제 풀이의 흐름이 이해가 됐다면
이번 문제에서는 '다중 리스트 정렬'과 '변수값 저장' 이 핵심이라는 것을 알 수 있다.
그럼 밑에서 마저 코드 작성에 대한 개념을 익혀보자🤗🥕


2. 다중 리스트 정렬

# 아래 코드에 대한 설명!
time = sorted([list(map(int, stdin.readline().split())) for i in range(N)])
time = sorted(time, key = lambda time : time[1])

리스트의 정렬이 필요한 문제는 여러번 접했기 때문에 sort()는 익숙했다.
만약 그런데 다중 리스트일 경우에 sorted를 사용한다면?

# sorted 예시
list = [[1, 4], [3, 5], [2, 13], [0, 6]]
print (sorted(list))

> [[0, 6], [1, 4], [2, 13], [3, 5]]

각 리스트의 [0]에 해당하는 값을 기준으로 오름차순 정렬이 된 결과를 볼 수 있다.
이 방법으로 '시작 시간'을 기준으로 정렬을 할 수는 있지만
[1]에 해당하는 값인 '종료 시간'에 반영하기 어렵다.

이럴 때는 람다(lambda)를 이용해 정렬을 해주면 된다.

# lambda sorted 예시
list = [[1, 4], [3, 5], [2, 13], [0, 6]]
print(sorted(time, key = lambda time : time[1]))

> [[1, 4], [3, 5], [0, 6], [2, 13]]

key 인자에 함수를 넘겨주고, 해당 함수의 반환값을 비교해서 정렬하는 방식인데
time[1]을 쓰면 [1]에 해당하는 값들을 전부 비교해서 정렬해준다고 이해하면 된다.

3. 종료 시간 저장하고 비교하기

# 아래 코드에 대한 설명!
for i in range(len(time)):
    if time[i][0] >= start:
        start = time[i][1]
        cnt += 1

여기 코드는 이해하기 쉬울 것이다.
종료 시간을 start 변수에 저장해두고, 각각 리스트의 시작 시간과 비교하면서
회의 시작 시간이 start보다 클 때 cnt += 1을 해준다.

최종적으로 cnt의 값은 회의 최대 개수이다.


profile
기록으로 나를 표현하다

0개의 댓글