문제 분석

이전 문제 와 비슷한 유형이다. 차이점은 지난번 문제는 하나의 수직선에 겹치지 않게 최대한 많은 선분을 배치하는 것이라면 이번 문제는 서로 겹치지 않는 선분을 합쳤을 때 최소 몇개의 선분이 남는지 구하는 문제이다.

저번 문제와 비슷하지만 조금 더 복잡해서 풀이를 생각해보고 코드를 작성해보다가 아이디어가 떠오르지 않아 다른 사람의 풀이를 확인했다

Key idea

이 문제도 그리디 알고리즘의 관점으로 생각해보면 한번에 최대한 많은 선분을 연결하면 남아있는 선분의 개수가 최소가 될 것이다. 그렇게 하기 위해서는 최대한 빈틈없이 선분을 이어붙여야 하고, 따라서 선분이 끝나는 위치에 가장 가까운 곳에서 시작하는 선분을 이어붙이면 된다.

이를 구현하기 위해서는 전체 선분을 앞에서부터 탐색하면서 새로운 선분을 확인할 때마다 기존 선분에 이어붙일 수 있는지 확인한 뒤 가능하다면 기존 선분에 이어붙이고, 불가능하다면 별도의 공간에 선분을 보관한다.

여기에서 내가 놓쳤던 부분이 있는데, 나는 새로운 선분을 이어붙이기 위해서는 현재 살아있는 모든 선분을 조사해봐야 한다고 생각했었다. 그런데 생각해보면 선분들이 이미 시작위치를 기준으로 정렬되어있으므로 이후에 조사할 선분들은 모두 현재 선분보다 뒤에 있는 것들이다. 그리고 최종적으로 남아있는 선분의 수가 최소가 되게 하기 위해서는 최대한 빈공간 없이 선분을 이어붙여야 하기 때문에 현재 선분을 이어붙이기 위해서는 살아있는 선분 중 가장 먼저 끝나는 선분만 조사를 하면된다.

즉, 정리하면 아래와 같은 순서로 문제를 풀 수 있다

1. 시작위치를 기준으로 선분을 정렬
2. 살아있는 선분 중 가장 먼저 끝나는 선분이 현재 선분의 시작위치보다 먼저 끝나면 선분을 이어붙임
3. 없으면 선분을 추가

Solution

위의 아이디어를 구현하기 위해서는 살아있는 선분 중 가장 먼저 끝나는 선분을 항상 알고있어야 하기 때문에 힙(우선순위 큐)을 사용한다. 새로운 선분을 조사할 때마다 힙에 선분이 끝나는 위치를 보관하고, 선분을 이어붙이려면 힙의 root를 꺼내고(가장 먼저 끝나는 선분) 이어붙인 선분이 끝나는 위치를 새롭게 힙에 push한다(선분을 이어붙임).

n = int(sys.stdin.readline())

schedules = []
for i in range(n):
    s = tuple(map(int, sys.stdin.readline().strip().split(" ")))
    schedules.append(s)

schedules.sort()

hq = []

heapq.heappush(hq, schedules[0][1])
for i in range(1, n):
    heapq.heappush(hq, schedules[i][1])
    if hq[0] <= schedules[i][0]:
        heapq.heappop(hq)

print(len(hq))

• BOJ 11000 강의실 배정