[백준] 1781번 : 컵라면

1781번: 컵라면

1781번: 컵라면

🤔 문제분석

두 가지의 풀이방식이 존재하는데 저번에 풀었던 문제의 유형중에서 완전 똑같은 문제의 유형이라 쉽게 문제를 풀이 하였습니다.

첫번째 방법으로는 서로소 집합을 활용하여 문제를 해결합니다. 서로소 집합으로 풀때에는 컵라면의 개수를 기준으로 내람차순 정렬하고 배열을 순회하면서 해당 노드의 (데드라인, 데드라인-1)을 유니온하여 다음의 리터레이션에서 부모노드를 데드라인-1 을 가르키도록 만들어 여러개를 넣을 수 없게 만듭니다.

두번째 방법으로는 우선순위 큐를활용하여 문제를 해결합니다. 데드라인을 오름차순으로 정렬한뒤 배열을 순회하면서 우선순위 큐에 가중치를 넣습니다. 여기서 배열의 길이가 현재 리터레이션에서의 데드라인보다 클경우 가장 작은 컵라면의 개수를 pop 시킵니다.

💻 코드

서로소 집합

import sys
input = sys.stdin.readline

N = int(input())

parent = [i for i in range(N+1)]

def union(v1, v2):
    p1 = parent[v1]
    p2 = parent[v2]
    if p1 > p2:
        parent[p1] = p2
    else:
        parent[p2] = p1
        
def find(v1):
    if parent[v1] != v1:
        parent[v1] = find(parent[v1])
        return parent[v1]
    else:
        return parent[v1]

problem = []
for _ in range(N):
     a, b = map(int, input().split())
     problem.append((a, b)) # 데드라인, 컵라면수

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

ans = 0
for deadline, score in problem:
    day = find(deadline)
    if day > 0:
        union(day, day-1)
        ans += score
        
print(ans)

우선순위 큐

import sys
import heapq

input = sys.stdin.readline

N = int(input())

problem = []
for _ in range(N):
     a, b = map(int, input().split())
     problem.append((a, b)) # 데드라인, 컵라면수

problem.sort(key=lambda x:x[0])

queue = []
for deadline, score in problem:
    heapq.heappush(queue, score)
    
    if len(queue) > deadline:
        heapq.heappop(queue)

print(sum(queue))

🎯 피드백 및 개선사항

저번에 풀었던 문제로 깔끔하고 빠르게 문제를 해결하였습니다.