[알고리즘/그리디] 1931 번 : 회의실 배정 - python

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

 

---

• 문제
• 소요 시간 : 실패

 

---

• 설계하기(접근방법) 

1. 총 회의 개수를 입력받는다

2. 1번만큼 for문을 통해 이중배열의 형태로 입력받는다

 

해결방법 떠올리기(실패)

해법:

1. 끝나는 시간이 빠를수록, 다음 회의를 더 많이 잡을 수 있다.

 

2. 끝나는 시간이 같은 회의시간이 여러개인 경우 :  1번 의 정렬을 마친 후, 시작 시간을 기준으로 오름차순 정렬한다.

Ex) 

3 3 

3 3 

3 4 의 경우 만약

 

3 4

3 3

3 3 으로 정렬되어있다면 뒤의 두 개의 회의는 포함되지 않는다. 문제의 조건에 시작과 끝이 같은 경우도 포함한다고 했기 때문이다.

따라서 정렬을 할 때 람다식을 이용해 lambda x : (x[1], x[0])을 키값으로 정렬한다

여기서 x[1] 은 끝나는 시간, x[0]은 시작 시간이다.

 

3. 회의 개수를 count할때,

맨 처음의 회의는 항상 포함되니 cnt = 1로 선언하고 endtime은 첫 회의의 종료시간으로 해준다

처음 케이스를 처리했으니 for문을 순회할 때 range는 1부터 n까지로 설정한다.

마지막으로 카운트되었던 회의의 종료시간과 현재 for문에서 순회하고 있는 시작시간을 비교하여 후건이 같거나 크면

cnt += 1을 해주고 endtime을 후건의 종료시간으로 바꾸어준다

 

4. cnt를 출력한다

 

 

---

• 코드(출력)

import sys

input = sys.stdin.readline

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

for i in range(n):
    meetlist.append(list(map(int, input().split())))

meetlist.sort(key=lambda x: (x[1], x[0]))
cnt = 1
endtime = meetlist[0][1]  # 4

for i in range(1, n):
    if endtime <= meetlist[i][0]:
        cnt += 1
        endtime = meetlist[i][1]

print(cnt)

---

• 얻어갈 부분

1. sys.stdin.readline 를 사용한 것과 안한 것의 시간 차이이다. 처음부터 sys를 쓰려고 하지는 말아도,

내 코드가 충분히 논리적이고 가독성이 좋았다고 생각했는데 시간이 초과된다면 적극 사용하자.

2. lambda 함수의 역할을 알게되었고, sort 함수에서 키 값으로 어떤 역할을 하는지 알게되었다.