백준 / 회의실 배정 / 1931번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 회의실 배정 / 1931번 (실버 1단계)

문제 사이트: https://www.acmicpc.net/problem/1931

 

문제 설명

---

나의 풀이

def solution(m):
    count = 0

    # end는 현재 회의 끝나는 시간
    end = -1

    # s는 다음 회의 시작, e는 다음 회의 끝
    for s, e in m:
        if end <= s:
            count += 1
            end = e

    return count

N = int(input())

meeting = []

for _ in range(N):
    # i, j = 회의 시작 시간, 회의 끝나는 시간
    i, j = map(int, input().split())
    meeting.append([i, j])

meeting.sort(key = lambda x: x[1])

print(solution(meeting))

이 문제의 핵심은 회의 끝나는 시간을 오름차순(이게 우선적으로 와야함), 회의 시작하는 시간을 오름차순을 통해서 가장 많이 사용할 수 있는 회의 시간을 찾는 것이 중요하다.

 

하지만 위 풀이는 정답과 비슷하지만 반례가 발생한다. 회의 끝나는 시간을 오름차순을 했지만 회의 시작하는 시간을 오름차순을 하지 않았기 때문이다.

 

반례 시뮬레이션

1. 회의 목록: [(1, 4), (2, 4), (3, 4), (0, 4)]
2. 종료 시간으로 정렬한 결과: [(1, 4), (2, 4), (3, 4), (0, 4)] (정렬 전과 동일)
3. 첫 번째 회의 (1, 4) 선택 (end가 4로 업데이트)
4. 두 번째 회의 (2, 4)도 선택됨 (count가 2로 증가)
5. 세 번째 회의 (3, 4)도 선택됨 (count가 3로 증가)
6. 네 번째 회의 (0, 4)도 선택됨 (count가 4로 증가)

결과적으로 이 코드는 4를 출력하지만, 올바른 답은 1이어야 하는 반례가 발생한다.

def solution(m):
    count = 0

    # end는 현재 회의 끝나는 시간
    end = -1

    # s는 다음 회의 시작, e는 다음 회의 끝
    for s, e in m:
        if end <= s:
            count += 1
            end = e

    return count

N = int(input())

meeting = []

for _ in range(N):
    # i, j = 회의 시작 시간, 회의 끝나는 시간
    i, j = map(int, input().split())
    meeting.append([i, j])

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

print(solution(meeting))

해결하려면 먼저 시작 시간과 종료 시간이 같은 회의가 있는 경우, 종료 시간이 같다면 시작 시간을 기준으로 정렬해야 한다.

---

※ 알아야 할 것

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

람다 식을 이용하면 2차원 배열도 쉽게 정렬할 수 있다.