백준 1781번 : 컵라면

접근

1. 입력 받은 데이터를 데드라인 순, 컵라면 수가 큰 순으로 정렬
2. 데이터를 for문으로 하나씩 확인하면서 다음 절차대로 처리

• 데드라인이 시간 변수보다 작다면: 무시
• 데드라인이 시간 변수랑 같다면: 현재 res에 있는 최솟값보다 크다면 그 값과 대체 아니면 무시
• 데드라인이 시간 변수보다 크다면: 일단 추가

1차 시도

import sys
input = sys.stdin.readline

# input
n = int(input())
data = [list(map(int, input().split())) for _ in range(n)]

# 데드라인이 가까우면서 컵라면은 많은 순서대로 정렬
data.sort(key = lambda x : (x[0], -x[1]))

res = 0
time = 0
minvalue = 1e9
for i in range(n):
    deadline = data[i][0]
    value = data[i][1]
    if deadline < time:
        continue
    elif deadline == time:
        if value > minvalue:
            res += (value - minvalue)
    else:
        minvalue = min(minvalue, value)
        res += value
        time += 1

print(res)

단순히 그냥 가장 작은 값을 기록해두고 데드라인이랑 같을 때 가장 작은 값과 비교하여 총합을 업데이트 시키는 식으로 했다가 틀려버렸다. 사실 처음에 heapq를 이용하여 최솟값을 리스트에서 빼는 것을 고려했다가 갑자기 사고가 최솟값만 기록해두면 되겠네~ 로 바뀌어버리는 바람에 첫 시도는 틀려버렸다.

정답 코드

import sys
import heapq
input = sys.stdin.readline

# input
n = int(input())
data = [list(map(int, input().split())) for _ in range(n)]

# 데드라인이 가까우면서 컵라면은 많은 순서대로 정렬
data.sort(key = lambda x : (x[0], -x[1]))


"""
접근
1. 시간 변수 생성
2. 데드라인과 시간 변수
    데드라인이 시간 변수보다 작다면: 무시
    데드라인이 시간 변수랑 같다면: 현재 res에 있는 최솟값보다 크다면 그 값과 대체 아니면 무시
    데드라인이 시간 변수보다 크다면: 일단 추가
"""
res = []
for i in range(n):
    deadline = data[i][0]
    value = data[i][1]
    time = len(res)
    if deadline < time:
        continue

    elif deadline == time:
        if value > res[0]:
            heapq.heappop(res)
            heapq.heappush(res, value)
    else:
        heapq.heappush(res, value)

print(sum(res))

저녁 먹고 다시 생각해보니, 처음 생각했던 대로 풀면 되는 문제라는 걸 깨달았다. 시간 별로 몇 개의 컵라면을 얻었는지 최소힙에 개수를 기록해두었다. for 문을 돌면서 데드라인과 최소힙 리스트의 요소 개수가 같을 경우 최소힙의 첫번째 요소와 문제의 컵라면 개수를 비교하여 문제의 컵라면 개수가 크다면, 리스트에서 최솟값을 버리고 문제의 컵라면 개수를 최소힙에 넣어주는 방식으로 해결하였다.