[실버 1] 1931번: 회의실 배정

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

1931번: 회의실 배정

---

문제

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

입력

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

출력

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

---

사고의 흐름

• 단순히 시작 시간이 가장 작은 회의나 회의 시간이 가장 작은 회의만을 계속 고르면 안돼.
• 가능한 모든 경우를 각각 리스트로 저장한 다음 크기가 가장 큰 리스트의 크기를 출력하면 되나? 근데 그건 그리디 알고리즘의 의의에 부합하지 않아.
• 만약 시작 시간이 어찌 되었건 끝 시간이 가장 이른 회의만을 선택한다면? 반례가 있나?
• 데이터가 0 5 / 1 2 / 2 3 / 3 4 와 같이 주어졌을 경우, 끝 시간을 기준으로 선택하면 0 5 를 거르고 바로 1 2 를 선택할 수 있어. 아무리 시작을 0시에 빨리 한들 끝 시간은 1 2 가 가장 이르니까. 이게 맞는 것 같다.
• 끝 시간을 기준으로 선택하면서 동시에 다음 회의의 시작 시간이 이전 회의의 끝 시간보다 이르다면 다음 회의는 선택하지 않고 넘어가면 되겠다.
• for문 range의 끝을 len(list)로 설정하고 for문 안에서 리스트 안의 원소를 삭제하면 반복문이 돌아갈 때마다 range의 len(list)가 하나씩 줄어들어서 새로 업데이트될까? 아니면 처음에 설정된 값으로 계속 유지될까? → 처음에 설정된 값으로 계속 유지된다.
• 리스트 컴프리헨션을 쓰는 게 싸게 먹히겠다!
• 근데 리스트 컴프리헨션을 쓸 때 조건문 안에서 이전 원소와 다음 원소를 인덱싱해서 비교할 수 있을까? 그게 안 되네...
• 그러면 반복문 돌리면서 리스트의 크기를 계속 체크해서 인덱스가 리스트의 크기를 넘어서면 break해줘야겠다.

 

• 88%에서 틀린다고...? 익스트림 케이스가 걸렸나보다. 반례를 찾아보자.
• 시작 시간과 끝 시간이 같은 경우, 즉 회의가 시작하자마자 끝나는 경우에서 문제가 생긴 듯 하다. 끝 시간을 기준으로만 정렬을 수행해서 데이터가 3 3 / 0 3 / 1 3 이 주어졌을 경우에는 정렬이 0 3 / 1 3 / 3 3 과 같이 이루어지지 않는다.
• 근데 이런 경우가 정답 도출에 영향을 미치나? 어쨌든 그게 그거 아닌가?
• 잘 모르겠어서 시작 시간 정렬까지 적용해서 백준에 제출을 해 보니 맞았다! 근데 왜 맞지?

내가 작성한 소스코드

import sys

n = int(sys.stdin.readline().rstrip())
meetings = []
for line in sys.stdin:
    meetings.append(list(map(int, line.split())))

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

i = 1
while True:
    if meetings[i][0] < meetings[i-1][1]:
        del meetings[i]
    else:
        i += 1

    if i == len(meetings):
        break

print(len(meetings))

피드백

• 시작 시간 정렬 안 했을 때 반례: https://www.acmicpc.net/board/view/98026
• for문이 돌아갈 때 range를 len(list)로 설정한 뒤 for문 안에서 리스트의 원소를 추가하거나 삭제해도 range의 len(list) 값은 초기에 얻은 값에서 변하지 않는다.
• sorted() 메서드에서 key 키워드에 lambda 함수를 사용하면 정렬 기준을 원하는 대로 선택해서 정렬할 수 있다. 만약 두 개 이상의 정렬 기준을 사용하면 앞에서부터 차례대로 적용된다.
• 개인적으로 간단하면서도 직관적으로 코드를 잘 짠 것 같다. 만족한다.