[백준/1913] 회의실 배정 | 그리디 | 우선순위 lambda 활용

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

1931번: 회의실 배정

오늘 문제해결기법 강의 시간에 그리디 알고리즘을 배웠다. 교수님께서 가르쳐주신 내용을 정리해보고자 한다. 그리디 알고리즘을 예전부터 알고있었는데 활용을 잘 하지 못했다! 이번 기회에 확실히 잡아두자.

알고리즘

그리디 알고리즘: Greedy(욕심쟁이)

 

[기본 마인드]

어떤 기준을 정하고 가장 최선의 선택을 먼저 시작한다. ✅ 그리디 문제를 풀 때는 기준을 세우는 게 중요하겠다.

어떤 문제를 푸는데 도저히 생각이 안 날 때 일단 이거부터 써보자.

➡️ 아이디어 생각은 어렵지 않으나 구현이 어려울 수 있다.

 

⭐️ 내 아이디어를 실수하지 않고 잘 구현하는 것.

⭐️ 계속 문제를 풀어나가면서 자신감과 멘탈을 길러야 한다.

 

[회의실 배정 문제]

그리디 알고리즘을 구현한다고 해도, 여러가지 케이스가 존재한다.

1. 회의 시간이 짧은 것부터 고려해서 이미 넣은 회의와 충돌하지 않게
   
   • 회의 시간이 짧다고 하더라도 시간들이 겹치면 소용이 없다.
2. 다른 회의와 가장 적게 겹치는 회의부터
   • 이거는 완전탐색으로만 가능하지않나?
   • 그리고 구현이 어렵다..
3. 제일 빨리 끝나는 회의부터, 겹치면 다 빼버린다.
   • 고려할 가짓수가 많아진다.
   • 끝나는 시간이 같은 경우는 더 빨리 시작하는 순서대로 정렬되어야 케이스가 많아진다. (1 to 2, 2 to 2를 생각해보자.)

---

최종 코드

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

for _ in range(n):
    s, e = map(int, input().split())
    t.append([s,e])

# 회의 끝나는 시간이 빠른 순
t = sorted(t, key = lambda x: x[1])
# 회의 시작하는 시간이 빠른 순
t = sorted(t, key = lambda x: x[0])

cnt = 0
end = 0
for i,j in t :
    if i >= end:
        cnt += 1
        end = j

print(cnt)

 

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

for _ in range(n):
    s, e = map(int, input().split())
    t.append([s,e])
    
t = sorted(t, key = lambda x: (x[1],x[0]))

cnt = 0
end = 0 
for i,j in t :
    if i >= end:
        cnt += 1
        end = j

print(cnt)

 

그냥 한줄로 쓰자..

---

알게된 점

순서대로 회의를 넣으면 다음과 같은 이중 리스트가 저장된다.

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

lambda 함수를 이중리스트에 적용하면 알아서 각각의 내부 리스트를 인덱싱해주고 x[0], x[1]과 같이 내부리스트의 원소들을 인덱싱 할 수 있다. (원래는 이중리스트에 li[0]처럼 인덱싱을 하면 내부 리스트 첫번째 전체 원소가 출력됨.)

# 회의 끝나는 시간이 빠른 순
t = sorted(t, key = lambda x: x[0])
# 회의 시작하는 시간이 빠른 순
t = sorted(t, key = lambda x: x[1])