백준(BOJ) #1931 회의실 배정 python(파이썬) (맞왜틀? 삽질과 해결과정)

문제

---

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

입력

---

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

출력

---

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

예제 입력 1

---

예제 출력 1

---

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

---

4

💡

아이디어

1. 회의를 일찍 끝나는 순으로 배열한다.

2. 일단 냅다 첫번째 회의를 고르고 → 나머지 회의 중에 시작 시간이 이전 회의 끝나는 시간과 같거나 더 크면 선택한다.

예를 들어 첫번째 회의를 선택하는 것 부터 시작하겠다.

1	2	3	4	5	6	7	8	9	10	11	12	13	14
														→냅다선택
														→ 탈락
														→ 탈락
														→다음선택
														…

초기코드

import sys
# n은 회의의 수
n = int(sys.stdin.readline())
meetings = []
for _ in range(n):
    s, e = map(int, sys.stdin.readline().split())
    meetings.append([s,e])
select = []

s_m = sorted(meetings, key=lambda id:id[1])

for i in range(n):
    if not select:
        select.append(s_m[i])
    end = select[-1][1]
    if s_m[i][0] >= end:
        select.append(s_m[i])

print(len(select))

처음에 생각한 것은 다음과 같았다.

하지만 문제가 두 개 있었다.

💡 과정1

# 에러가 발생 한 부분
for i in range(n):
    if not select:
        select.append(s_m[i])
		    continue

이 코드는 처음 시작을 위한 코드였는데, 담고 나서 i가 변하지 않아서 처음 시작코드를 2번 담는 경우가 생겼다.

# input
2
1 1
2 3

# output = 3
# answer = 2

해결책

• 최초에는 담은 후 continue를 통해 바로 i를 1 증가 시켜주었다.

💡 과정2

# 에러가 발생 한 부분
s_m = sorted(meetings, key=lambda id:id[1])

이 코드는 회의가 빨리 끝나는 순서대로 정렬하기 위한 코드였는데, 문제의 가장 중요한 부분을 놓쳤다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 라는 부분이었다.

이것 때문에 회의의 끝나는 시간 뿐 만 아니라, 시작시간도 함께 정렬을 해 주어야 한다.

# input
3
4 4
3 4
5 7

# output = 2
# answer = 3

해결책

• 정렬할 때 key에 종료시간 이후 시작시간 까지 고려할 수 있도록 변경 해 주었다.

최종코드

import sys
# n은 회의의 수
n = int(sys.stdin.readline())
meetings = []
for _ in range(n):
    s, e = map(int, sys.stdin.readline().split())
    meetings.append([s,e])
select = []

s_m = sorted(meetings, key=lambda id:(id[1], id[0]))

for i in range(n):
    if not select:
        select.append(s_m[i])
        continue
    end = select[-1][1]
    if s_m[i][0] >= end:
        select.append(s_m[i])

print(len(select))

Uploaded by N2T