.PNG)
26. 회의실 배정(그리디)
한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들
려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하
면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중
단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
▣ 입력설명
첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정
보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.
▣ 출력설명
첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.
▣ 입력예제 1
5
1 4
2 3
3 5
4 6
5 7
▣ 출력예제 1
3
예제설명
(2, 3) , (3, 5), (5, 7)이 회의실을 이용할 수 있다.
<내 풀이>
처음 그리디 시간이라서 개념을 이해하고 다음 문제부터 적용해보기로..!
<풀이>
- 한 개의 회의가 끝나는 시간을 기준으로 정렬이 제일 좋다
- 현재 진행 회의의 끝나는 시간보다 다음 회의 시작 시간의 시간이 더 크거나 같아야 한다
lst=[]
n=int(input())
for _ in range(n) :
s,e=list(map(int, input().split()))
lst.append([s,e])
lst.sort(key=lambda x : (x[1], x[0])) #x[1]을 기준으로. 즉 리스트의 e기준으로 오름차순 정렬하라
et=0 #회의가 끝나는 시간
cnt=0
for s, e in lst :
if s>=et :
et=e
cnt+=1
print(cnt)<반성점>
- 그리디를 처음 배워서 반성할 점은 없는 것 같다
<배운 점>
-
그리디 알고리즘 :
문제를 풀어나가는 과정, 단계에 있어서
이 단계에서 현재 가장 좋은 것이 무엇인지 판별하고 그것을 선택하는 것
그리디 문제는 정렬을 한 다음 차례차례 선택해나가면 되는 것이다
정렬과 동반되어서 문제풀이가 된다 -
append할 때 두개의 요소를 한 튜플로 묶어서 넣어줄 수 있다
for _ in range(n) :
s,e=(map(int, input().split()))
lst.append((s,e))s,e=(map(int, input().split()))
lst.append(s,e) #이렇게 하면 두 원소를 append할 수 없다고 오류가 난다
lst.append((s,e)) #이렇게 하면 두 원소를 하나의 튜플(원소)로 받게 되어서 된다
- 리스트로 받고 싶을 때는
st.append([s,e]) 이렇게 받아주면 된다
-정렬할 때 뒷원소 기준으로 오름차순 하고 싶은 거면
lst.sort(key=lambda x : (x[1], x[0]))
#x[1]을 기준으로. 즉 리스트의 e기준으로 오름차순 정렬하라key 매개변수
강력한 sorted와 lambda
key 인자에 함수를 넘겨주면 해당 함수의 반환값을 비교하며 순서대로 정렬한다.
오름차순 정렬 : sorted(a, key=lambda x:x[0])
(==a.sort(key=lambda x : x[0])
내림차순 정렬 : sorted(a, key=lambda x:-x[0])
👉 와-우!!! '-' 마이너스만 붙여주면 내림차순으로 만들 수 있다 . . . !!!!
👉 요소가 여러개일 경우 각 요소마다 정렬기준을 정해줄 수 있다. sorted(a, key=lambda x: (x[0], -x[1])
(==a.sort(key=lambda x : (x[1], x[0]))=> 뒤에 있는 원소를 기준으로 오름차순 정렬해
👉 '-' 말고 reverse=True로도 내림차순 만들 수 있다.
