[백준 - Python] 1931. 회의실 배정 (그리디)

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

1931번: 회의실 배정

 

코드

import sys
n = int(sys.stdin.readline())

time = []
for i in range(n):
    s, e = map(int, sys.stdin.readline().split())
    time.append((s, e))

time.sort(key = lambda x : (x[1], x[0]))

cnt = 1
endTime = time[0][1]
for i in range(1, n):
    if time[i][0] >= endTime:
        cnt += 1
        endTime = time[i][1]

print(cnt)

 

아이디어도 생각을 못한 문제이다.

 

회의가 겹치지 않으면서 회의실을 사용할 수 있는 회의의 최대 개수를 구해야 하는데

회의의 최댓값을 구하기 위해서는,

첫 번째 회의부터 시작해서 해당 회의의 끝나는 시간과 가장 가까운 시작 시간을 가진 회의들 중,

끝나는 시간이 가장 빠른 회의를 선택해야 한다. (빨리 끝나야 더 많은 회의를 담을 수 있음)

 

따라서, (시작 시간, 끝 시간) 형태로 저장되어 있는 데이터를

우선 끝 시간이 빠른 순서대로 정렬을 한 후에,

끝 시간이 같은 경우에는 시작 시간이 빠른 순으로 정렬을 해주어야 한다.

 

이렇게 정렬을 해줘야 차례대로 리스트를 돌면서

현재까지 담은 회의 중 마지막 회의의 끝 시간과

탐색할 회의들의 시작 시간을 순차적으로 비교할 때,

현재 회의가 끝난 이후에 시작될 수 있는 회의 중 가장 빠르게 끝나는 최적의 회의를 담을 수 있다.

 

 

---

 

 

문제 관련 문법 정리

1. global 명령어

함수 내에서 정의된 변수를 함수 밖에서도 사용하고 싶을 때, global 명령어를 사용

apple = 100
def mart(rise):
    global apple
    apple = apple + rise
    print(apple)

print(apple)

 

하지만, 함수의 독립성을 고려해 사용을 지양한다.

 

2. lambda 함수

함수를 한 줄로 간단하게 표현하는 예약어이다.

total = lambda a, b, c : a+b+c
print(total(1,2,3))

 

위 코드의 실행 결과는 6이 나온다.

 

3. 리스트 정렬 시 key 사용(sort, sorted) / lambda 함수 활용

a = [(1, 2), (5, 1), (0, 1), (5, 2), (3, 0)]

b = sorted(a, key = lambda x : x[0])
print(b)

c = sorted(a, key = lambda x : x[1])
print(c)

 

위 코드의 실행 결과는 다음과 같다.

[(0, 1), (1, 2), (3, 0), (5, 1), (5, 2)]
[(3, 0), (5, 1), (0, 1), (1, 2), (5, 2)]

 

 

비교할 요소가 복수 개인 경우, 튜플로 우선 순위를 정해준다 .

d = sorted(a, key = lambda x : (x[0], x[1]))
print(d)

 

위 코드의 실행 결과는 다음과 같다.

[(0, 1), (1, 2), (3, 0), (5, 1), (5, 2)]

첫 번째 요소가 5인 원소가 2개이므로

그 둘에 대해서 정렬할 때에는 두 번째 요소를 기준으로 오름차순 정렬해준다.

 

 

현재 차순의 반대 차순으로 정렬하고 싶으면, - 부호를 붙여준다.

e = sorted(a, key = lambda x : -x[0])
print(e)

 

위 코드의 실행 결과는 다음과 같다

[(5, 1), (5, 2), (3, 0), (1, 2), (0, 1)]

첫 번째 요소를 기준으로 확인을 해보면

디폴트 차순인 오름차순의 반대 차순인 내림차순으로 정렬된 것을 확인할 수 있다.