그리디 문제 #1. 회의실 배정

*이 풀이는 인프런: 파이썬 알고리즘 문제풀이 강좌에 기반하였습니다.

 

 

 

 

내 풀이

 

풀지 못함..

 

 

 

 

강사님 풀이

 

import sys
sys.stdin=open("input.txt","rt")

n=int(input())
meeting=[]
for i in range(n):
    s,e=map(int,input().split())
    meeting.append((s,e))
    
meeting.sort(key=lambda x: (x[1],x[0]))
et=0
cnt=0

for s,e in meeting:
    if s>=et:
        et=e
        cnt+=1
print(cnt)

 

 

 

 

배운점

 

1.

그리디 알고리즘이란 현재 상황에서 가장 좋은 것을 고르는 알고리즘이다.

그렇기 때문에 정렬을 사용해서 가장 좋은 것부터 차례차례 선택해나가면 된다.

문제 상황에서 '가장 큰 순서대로', '가장 작은 순서대로' 등과 같은 기준을 제시한다면 그리디 알고리즘을 떠올리자.

 

이 문제에서는 '최대로 사용할 수 있는 회의의 수'를 구하라고 했으므로 그리디 알고리즘을 떠올릴 수 있었다.

문제를 푸는 데 중요한 키포인트는 회의가 언제 끝나는 지이다. 회의가 끝나야 다음 회의를 진행할 수 있기 때문이다.

그래서 회의의 끝나는 시각을 기준으로 정렬하여 가장 빨리 끝나는 회의부터 선택해 나갔다.

 

2.

sort( )의 인자 key :

key값으로 정렬을 목적으로 하는 함수를 넣는다. 주로 람다함수를 이용한다.

key값을 기준으로 정렬되는데, 기본값은 오름차순이며 내림차순으로 정렬하고 싶다면 -를 붙인다.

여러가지 기준을 고려해서 정렬하고 싶다면 key값에 튜플 형태로 전달하면 된다.

 

강사님 코드에서 meeting.sort( key = lambda x: ( x[ 1 ], x[ 0 ] )의 의미는

람다함수의 x값으로 ( s, e ) 튜플이 들어오고, ( x[ 1 ], x[ 0 ] ) 튜플을 반환한다.

이 두가지를 key값으로 받아 먼저 x[ 1 ]( = end ) 값을 기준으로 오름차순 정렬을 하고,

동일한 값이 있다면, x[ 0 ]( = start ) 값을 기준으로 오름차순 정렬한다.

만약 -x[ 0 ]이라면 내림차순으로 정렬한다.