[백준 14464번] 소가 길을 건너간 이유 4 (Python3)

from heapq import *

def solve():
  result = 0; hq = []; i = -1
  for c in ch:
    for i in range(i+1,N):
      s,e = cow[i]
      if s>c:
        i -= 1
        break
      heappush(hq,(e,s))
    while hq:
      e,s = heappop(hq)
      if c<=e:
        result += 1
        break
  return result

C,N = map(int,input().split())
ch = sorted(int(input()) for i in range(C))
cow = sorted([*map(int,input().split())] for i in range(N))
print(solve())

우선순위 큐를 이용해서 해결하였다.

처음엔 단순한 정렬+스택 문제라고 생각했다. 그러나 틀렸습니다를 몇 번 겪고 나서 그렇게 풀 수 있는 문제가 아니라는 사실을 알게되었다.

 

풀이를 설명하면,

1. 닭과 소를 정렬한다. 소는 start를 기준으로 정렬한다.

2. 가장 작은 닭부터 닭이 포함될 수 있는 범위까지의 소를 heapq에 담는다. 이때 heapq는 start가 아닌 end를 기준으로 정렬한다.

3. 현재 닭을 포함하지 않는 소는 전부 버리고, 남은 소 중 end가 가장 작은 값을 pop한 뒤 개수를 +1 한다.

4. 결과를 출력한다.

 

문제를 다 풀고 나서 난이도 기여내역을 보니 약 3달 전에 풀었던 보석도둑 [백준 1202번] 보석 도둑 (Python3) (tistory.com) 과 거의 유사하다는 것을 알게되었다. 당시에도 꽤 어렵게 해결했던 문제였는데, 3달만에 다시 보니 이번에도 골치를 앓게 한 문제였다.

 

 

오늘의 교훈) 이전에 풀었던 방식을 적재적소에 활용하자