[Algorithm] 프로그래머스 - 야근 지수

문제

[프로그래머스] 야근 지수

사용 알고리즘

- Heap / Greedy

- 우선순위 큐 (PriorityQueue)

- 시간복잡도 O(n logN) (n: 남은 시간, N: 작업 수)

해결방법

• 주어진 works를 우선순위 큐에 작업량이 많은 순으로(내림차순) 넣는다
• 남은 작업시간 n 동안 반복문을 돌면서, 가장 많은 작업량을 가진 일을 찾아서(조회) 1씩 줄이고 다시 큐에 넣는다
  • 이 동작을 효율적으로 처리하기 위해 힙 구조를 사용

소스코드

사용언어 : java

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>(works.length, Collections.reverseOrder());
        for (int w : works) pq.offer(w);
        
        while (n-- > 0 && !pq.isEmpty()) {
            int maxWork = pq.poll();
            if (maxWork <= 0) break;
            pq.offer(--maxWork);
        }
        
        for (int w : pq) {
            answer += (long) w*w;
        }
        
        return answer;
    }
}

PriorityQueue<Integer>

• 기본은 Min Heap (오름차순)
• 가장 큰 값을 꺼내기 위해 Collections.reverseOrder()를 사용해 Max Heap으로 만든다

방식	가장 큰 값 조회	시간복잡도	desc
정렬된 배열 (List, Array등) 유지	O(1) 조회 가능	❌ 하지만 삽입 시 O(N)	매번 삽입/삭제 느림
PriorityQueue(Heap)	O(log N)	✅ 삽입/삭제 모두 log N	효율적
매번 정렬 (sort)	O(N log N) * n	❌ 매우 비효율적

 

 

(힙 정리)

자료구조 형태	완전 이진 트리 (Complete Binary Tree)
정렬 규칙	부모 노드 ≥ 자식 노드 (Max Heap) / ≤ 자식 노드 (Min Heap)
대표 구현	PriorityQueue (Java 표준 라이브러리에서 Heap 기반으로 구현됨)
주요 기능	“가장 큰(작은) 값”을 O(1) 로 조회, O(log N) 으로 삽입/삭제

 

 

 

내부 구조

완전 이진 트리(complete binary tree) 구조 (왼쪽부터 차례로 채워짐)

예) Max Heap (부모 ≥ 자식) 구조:

          9
       /     \
      7       8
     / \     / \
    3   5   2   6

 

배열 표현

index:  0  1  2  3  4  5  6
value: [9, 7, 8, 3, 5, 2, 6]

 

 

부모-자식 인덱스 관계

노드	왼쪽 자식	오른쪽 자식	부모
i	2*i + 1	2*i + 2	(i-1)/2

 

삽입(offer) 시 동작 — “위로 올리기 (heapify up)”

새 원소를 마지막에 추가한 후, 부모와 비교해서 힙 조건(부모 ≥ 자식) 을 만족할 때까지 올라간다.

예)

기존 힙: [9, 7, 8]
삽입: 10

배열: [9, 7, 8, 10]

 

이제 10은 부모(7)보다 크므로 자리 교환

[9, 10, 8, 7]

 

다시 비교 → 10은 부모(9)보다 크므로 한 번 더 교환

[10, 9, 8, 7]

완료

삽입 복잡도: O(log N)

(트리의 높이만큼만 올라가면 됨)

 

 

삭제(poll) 시 동작 — “아래로 내리기 (heapify down)”

poll() 은 항상 루트(가장 큰 값) 을 꺼낸다

[10, 9, 8, 7]  → poll() → 루트(10) 삭제

 

이때, 마지막 노드(7)를 루트로 올려놓고 “힙 재정렬” 시작

[7, 9, 8]

 

부모(7) < 자식(9, 8) → 더 큰 자식(9)과 교환

[9, 7, 8]

힙 속성 복구 완료 

 

삭제 복잡도: O(log N)

(트리의 높이만큼만 내려가면 됨)

 

정렬 기준에 따른 힙 종류

Min Heap	부모 ≤ 자식	new PriorityQueue<>() (기본)
Max Heap	부모 ≥ 자식	new PriorityQueue<>(Collections.reverseOrder())

 

Java의 PriorityQueue는 내부적으로 배열 기반의 힙 구조로 동작

public class PriorityQueue<E> extends AbstractQueue<E> {
    private transient Object[] queue; // 힙을 배열로 저장
    private int size = 0;             // 현재 원소 개수
    ...
}

• 삽입 시 siftUp()
• 삭제 시 siftDown()

이라는 메서드로 heapify 과정을 수행

 

시간 복잡도

삽입 (offer)	O(log N)
삭제 (poll)	O(log N)
최대값/최소값 조회 (peek)	O(1)

 

 

 

한줄평

첨에 그냥 List로 풀었다가 효율성 테스트에서 실패떠서, 우선순위큐로 바꿨더니 해결되었다. . .

그냥 느끼기엔 둘 다 내부적이든 외부적이든 정렬하는 거니까 똑같은 시간복잡도를 가질 것 같은데, 우선순위큐는 완전 이진 트리 형태라 삽입 삭제가 O(log N)만에 동작한다는 게 큰 장점인 것 같다 : ) . . .