[코테/백준] Python 회의실 배정 - 1931번 (실패)

실패 | 시도 - 번

 

🔗 [백준] 1931번 회의실 배정

1931 : [그리디 알고리즘] 회의실 배정(py)

---

문제 설명

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

---

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

---

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

---

입력과 출력 예시

입력	출력
11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14	4

 

---

내 소스

• 첫시도 : 실패 (구현 실패)

n = int(input())
times = []
for _ in range(n):
    times.append(list(map(int, input().split())))
times.sort(key=lambda x: (x[1], x[0]))    
cnt = 1
meeting = times[0]
for i in range(1, len(times)):
    if meeting[1] <= times[i][0]:
        cnt += 1
        meeting = times[i]
print(cnt)

 

소스 설명

n = int(input())
times = []
for _ in range(n):
    times.append(list(map(int, input().split())))

[1 - 4] : 회의 횟수를 입력받고 for문을 이용하여 회의 시작 시간과 종료 시간을 리스트 형태로 변환하고 times 리스트에 추가한다. 

 

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

[5] : 회의 끝나는 시간을 기준으로 오름차순 후, 회의 시작하는 시간을 기준으로 오름차순 정렬한다. 

 

cnt = 1
meeting = times[0]
for i in range(1, len(times)):
    if meeting[1] <= times[i][0]:
        cnt += 1
        meeting = times[i]

[6 - 11] : 첫 회의를 meeting 변수에 담기 때문에 cnt는 1을 갖는다. 뒷 회의 시작 시간이 앞 회의의 종료 시간과 같거나 크면 cnt에 1을 추가하고 기준을 바꾸기 위해 meeting에 times[i]를 저장한다.   

---

다른 코드 분석

- 많은 회의 수를 갖기 위해 끝나는 시간의 오름차순, 시작하는 시간의 오름차순으로 정렬한다. 

🔗 백준 1931번 반례

예) 회의 5개

(6, 7)

(6, 6)

(5, 6)

(5, 5)

(7, 7)

 

→ 회의가 빨리 끝나야 시작할 수 있는 회의들이 많아진다. 그래서 종료 시간 기준으로 오름차순을 하되, 시작 시간 기준도 같이 오름차순으로 해줘야 한다. 

• 종료 시간 기준 오름차순 : [[5, 5], [6, 6], [5, 6], [6, 7], [7, 7]] → 최대 회의 개수 : 4개 
• 종료 시간 기준 오름차순, 시작 시간 기준 오름차순 : [[5, 5], [5, 6], [6, 6], [6, 7], [7, 7]] → 최대 회의 개수 : 5개 

times = [[6, 7], [6, 6], [5, 6], [5, 5], [7, 7]]

times.sort(key=lambda x: (x[1]))
print(times)
# 결과 : [[5, 5], [6, 6], [5, 6], [6, 7], [7, 7]]

times.sort(key=lambda x: (x[1], x[0]))
print(times)
# 결과 : [[5, 5], [5, 6], [6, 6], [6, 7], [7, 7]]

---

회고

- 많은 회의 수를 갖기 위해 회의 시간이 짧으면서 그 다음으로 빨리 시작할 수 있는 회의를 찾을 수 있게 로직을 짜려고 했다. 내가 막혔던 부분은 어느 회의를 먼저 시작해야할 지였다. 빨리 시작하면서 빨리 끝나는 회의를 먼저 정해야 뒷 부분도 쉽게 로직을 짤 수 있다고 생각했는데 그 로직을 못 짜서 아래 코드에서 멈추게 되었다. 

# 실패코드입니다.
n = int(input())
times = []
for i in range(n):
    times.append(list(map(int, input().split())))
times.sort(key=lambda x:(x[0], x[1]-x[0]))
start = times[0]
cnt = 1
for time in times:
    if start[1] - start[0] > time[1] - time[0]:
        start = time
    if start[1] <= time[0]:
        cnt += 1
        start = time
print(cnt)

- 1차원 리스트는 많이 sort 해봤는데 2차원 리스트의 정렬은 아직 생소한 것 같다. 공부를 좀 해야할 것 같다. 

 

🔗 리스트 정렬

---

Ref. 

1. 문제 풀이 / https://suri78.tistory.com/26

2. 문제 풀이 / https://jokerldg.github.io/algorithm/2021/03/11/meeting-room.html

3. 문제 풀이 / https://hongcoding.tistory.com/22

4. 문제 풀이 / https://kbwplace.tistory.com/128

---

* 잘못된 부분에 대해 댓글 남겨주시면 감사하겠습니다! 😀