소가 길을 건너간 이유 4 (14464번) - 백준 (BOJ)

https://www.acmicpc.net/problem/14464

14464번: 소가 길을 건너간 이유 4

 

 

백준 - 소가 길을 건너간 이유 4 (Why Did the Cow Cross the Road (Silver)) (14464번)

 

난이도 : Gold 1

알고리즘&자료구조 : 우선순위 큐 (Priority Queue) & 정렬 (Sorting)

시간복잡도 (Time Complexity) : O( (N+C) * log(N+C) )

---

★ 핵심 Idea ★

 

◎ 소와 닭 배열을 합쳐서 한 번에 정렬한다.

◎ 우선순위 큐를 활용해서,
현재 이동 가능한 소들 중 건널 수 있는 마감시간이 가장 임박한 소와 현재 닭을 매칭시켜준다.

 

 

< 전체 코드 >

 

import sys
input = sys.stdin.readline
from heapq import heappush, heappop


class Farm():
    def __init__(self, C, N):
        stocks = [(int(input()),) for _ in range(C)] + [tuple(map(int, input().split())) for _ in range(N)]
        stocks.sort(key=lambda x: (x[0], -len(x)))
        pq = []
        pairs = 0
        for ls in stocks:
            if len(ls) == 2:
                heappush(pq, ls[1])
            else:
                while pq and pq[0] < ls[0]:
                    heappop(pq)
                if pq:
                    heappop(pq)
                    pairs += 1
        self.pairs = pairs


if __name__ == '__main__':
    farm = Farm(*map(int, input().split()))
    print(farm.pairs)

---

 

예제 입력 1

5 4
7
8
6
2
9
2 5
4 9
0 3
8 13

 

 

① 입력받은 닭과 소 배열을 합한 다음

첫 번째 원소의 오름차순으로 정렬하고

첫 번째 원소가 같다면, 소가 닭보다 먼저 오게 정렬한다.

 

stocks = [(int(input()),) for _ in range(C)] + [tuple(map(int, input().split())) for _ in range(N)]
stocks.sort(key=lambda x: (x[0], -len(x)))

0 3
2 5
2
4 9
6
7
8 13
8
9

 

 

 

② 정렬된 배열을 순서대로 탐색한다.

pq = []
pairs = 0
for ls in stocks:
    if len(ls) == 2:
        heappush(pq, ls[1])
    else:
        while pq and pq[0] < ls[0]:
            heappop(pq)
        if pq:
            heappop(pq)
            pairs += 1

 

현재 원소의 길이가 2라면 (즉, 소에 대한 정보라면)

우선순위 큐 "pq"에 소가 건널 수 있는 마감 시간을 삽입한다.

 

if len(ls) == 2:
    heappush(pq, ls[1])

 

현재 원소의 길이가 1이라면 (즉, 닭에 대한 정보라면)

먼저 닭이 도울 수 있는 시간보다 앞서 마감된 소의 정보를 "pq"에서 제거한다.

 

그리고 "pq"에 소의 정보가 남아았다면, 마감 시간이 가장 임박한 소를 도와서 길을 건넌다.

(즉, 소가 닭의 도움을 받았으므로 pairs에 1을 더해준다.)

 

else:
    while pq and pq[0] < ls[0]:
        heappop(pq)
    if pq:
        heappop(pq)
        pairs += 1

 

 

 

③ pairs를 출력한다.

 

self.pairs = pairs

if __name__ == '__main__':
    farm = Farm(*map(int, input().split()))
    print(farm.pairs)