[코드트리 조별과제] 실전훈련 릴레이 문제 풀기

나름 자신있게 구글링해서 풀면 되겠지하고 코드트리 릴레이문제 풀기에 들어갔다
첫번째 문제는 무난하게 풀었는데 두번째 문제가 자료구조를 사용해서 그리드알고리즘 방식으로 푸는 문제였는데
쉽지 않았다.

문제에 저작권이 있는지 모르겠어서 일단 포스팅에 포함하지 않겠다.

무튼 딱 풀었을 때 만점이 안나오더라, 코드트리의 장점이 틀린 테스트 케이스를 공개해준다는 건데 
테스트 케이스가 너무 커서 윤곽이 안보이더라,, 그래서 아우.. 왜 틀렸는지 잘 모르겠더라..

그래서 문제 유형을 좀 보고 우선순위 큐라고 되어 있길래 우선순위 큐로 바꾸어서 풀었음에도 만점이 안나오더라....

그래서 ..! 그래서...! 결국 해답을 봤다.
(이게 시간적 이득이긴함.. 할만큼 했음)

근데 아 최소힙으로 간단하게 풀 수 있었던 문제였다.... 평소에 최소힙을 많이 써본적이 없어서 
못풀만 했다.. 그런 느낌이다.

import heapq

# 최소 힙을 사용하여, 낮은 가격의 주문을 먼저 제거합니다.
min_heap = []
# (희망하는 시간, 가격) 쌍을 저장하는 리스트입니다.
orders = []
total_price = 0  # 처리할 수 있는 주문의 총 가격

# 주문의 수를 입력받습니다.
n = int(input())
for _ in range(n):
    price, day = map(int, input().split())
    # 희망하는 시간(day) 순으로 정렬하기 위해 (day, price) 쌍으로 저장합니다.
    orders.append((day, price))

# 주문을 희망하는 시간(day)에 따라 정렬합니다.
orders.sort()

for order in orders:
    # 현재 주문을 최소 힙에 추가하고 총 가격에 더합니다.
    heapq.heappush(min_heap, order[1])
    total_price += order[1]

    # 만약 처리 가능한 시간보다 더 많은 주문이 존재한다면,
    # 가장 낮은 가격의 주문을 제거합니다.
    if len(min_heap) > order[0]:
        total_price -= heapq.heappop(min_heap)

# 처리할 수 있는 주문의 최대 가격 합을 출력합니다.
print(total_price)

 이런 자동정렬을 포함하는 자료구조는 확실히 코드짤 때 편리한 면이 있는 듯하다. (잘 활용하지 못하지만)
물론 내부 정렬 방식을 살펴보고 시간복잡도에 대해서 알고서 사용하는 것 또한 중요하다고 생각은 한다.

 

알고리즘... 자료구조 부터 차근차근 해야하는데.. 너무 귀찮긴하다.