백준1931 회의실 배정 파이썬

백준 1931 회의실 배정
링크텍스트

n = int(input())
data = [[0,0]]
meeting_count =0
last_time =0
for _ in range(n):
    start, end = map(int,input().split())
    data.append([start,end])

data = sorted(data,key = lambda a:a[0])
data = sorted(data,key = lambda a:a[1])

for i,j in data:
    if i>=last_time:
        meeting_count+=1
        last_time = j

print(meeting_count)

Greedy 문제

문제풀이

• 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
• 끝나는 시간 순서대로 정렬후, 일찍 끝나는 회의부터 탐욕적으로 선택을 하면된다.

위 와 같은 풀이를 생각해내는 것은 쉽지 않은 것 같다. 하지만 문제를 손으로 직접 써서 문제의 규칙을 확인해 봄으로서 위와 같은 아이디어를 도출해 낼 수 있다.

사용 함수

이 문제를 풀면서, sorted 함수를 정리해 보자
a = sorted(a, lambda x: x.modified, reverse=True)
x.modified 에 a[0]= 시작시간, a[1] = 종료시간으로 키값을 설정해 정렬을 수행 할 수 있다.

ex)

lst = [('candy','30','100'), ('apple','10','200'), ('baby','20','300')]
lst.sort(key=lambda x:x[1])
print(lst)
## 출력 list 의 첫번째 값인 이름으로 정렬 된것을 볼 수 있다.
[('apple', '10', '200'), ('baby', '20', '300'), ('candy', '30', '100')]

느낀점

Greedy 문제를 앞으로 5문제 정도 풀면서 탐욕적 방법의 익숙해질 필요가 있다고 생각한다.

알고리즘을 java로만 풀다가 python으로 바뀌면서 생각이 좀 더 유연해 진것같은 느낌이 든다.