[프로그래머스] 야근 지수(python) / 힙

💻 프로그래머스 - 야근 지수 문제

👉 문제 보러 가기

 

---

🧠 문제 접근 방식

야근 지수 문제를 해결하기 위해 처음에는 리스트를 매번 내림차순 정렬하면서, 가장 큰 작업량을 가진 작업자의 작업량을 1씩 감소시키는 방식으로 접근했습니다.

def solution(n, works):
    answer = 0
    sorted_works = sorted(works, reverse=True)
    i = 0

    while i < n:
        sorted_works = sorted(sorted_works, reverse=True)
        if sorted_works[0] == 0:
            break
        else:
            sorted_works[0] -= 1
        i += 1

    for num in range(len(sorted_works)):
        answer += sorted_works[num] * sorted_works[num]

    return answer

정렬 방식 결과

⚠️ 문제점: 효율성 실패

• sorted()를 매 루프마다 호출 → O(n log n) 시간 복잡도
• 작업량이 많아질수록 성능 저하 → 효율성 테스트 실패

 

---

🔑 해결 방법: 힙(Heap) 자료구조 사용

Heap은 최댓값 또는 최솟값을 빠르게 꺼낼 수 있는 자료구조입니다.
이 문제에서는 최대 작업량을 빠르게 줄이기 위해 최대 힙을 사용해야 합니다.

Python의 heapq는 최소 힙(min-heap)을 기본으로 제공하기 때문에, 음수로 변환하여 최대 힙처럼 사용할 수 있습니다.

import heapq

def solution(n, works):
    answer = 0

    # 최대 힙처럼 사용하기 위해 음수로 변환
    works = [-work for work in works]
    heapq.heapify(works)

    for _ in range(n):
        if works[0] == 0:
            break
        max_work = -heapq.heappop(works) - 1
        heapq.heappush(works, -max_work)

    # 최종 야근 지수 계산
    for work in works:
        answer += work * work  # works에는 음수값이지만 제곱되면서 양수가 됨

    return answer

힙 방식 결과

🔍 코드 해설

• heapq는 최소 힙 기능만 지원 → 음수로 변환해서 최대 힙처럼 사용
• heapq.heappop()은 가장 작은 원소를 꺼냄 (음수 기준, 즉 가장 큰 값)
• for _ in range(n):에서 _는 반복만 필요하고 값은 필요 없을 때 사용

 

---

✨ 마무리 정리

처음엔 단순 정렬 방식으로 정확성을 만족했지만, 효율성 문제로 인해 힙 자료구조로 전환했습니다.
이 문제를 통해 자료구조 선택이 성능에 큰 영향을 미친다는 것을 느꼈고, heapq 라이브러리의 활용법도 익힐 수 있었습니다.

정렬 O(n log n) vs 힙 O(log n) 차이를 생각해보기

 

 

---

📌 아직 배우는 중이라 부족한 부분이 있을 수 있습니다.
혹시 잘못된 내용이나 더 나은 방법이 있다면 알려주세요 🙏
감사합니다! 😄