[programmers] 야근 지수 (Java)

[야근 지수]

https://school.programmers.co.kr/learn/courses/30/lessons/12927

프로그래머스

 

 

[접근 방식]

1. 'Arrays.sort 를 통해서, 리스트를 정렬하는 방법'의 경우, 효율성 검사에서 시간 초과로 문제를 해결할 수 없다.

 

2. '최대 힙을 이용하는 방법'을 통해 문제를 해결하였다.

" PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reversOrder()); " 를 통해

우선 순위 큐 + 내림 차순 정렬 = 최대 힙 

이 방식을 통해 최대 힙을 구현한다.

 

[Java 코드]

//https://school.programmers.co.kr/learn/courses/30/lessons/12927
//코딩테스트 연습 - 연습문제 - 야근 지수

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public long solution(int n, int[] works) {
        // 최대 힙 구현 - 우선순위 큐 + 내림차순 정렬
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        
        for (int work : works) {
            maxHeap.add(work);
        }

        for (int i = 0; i < n; i++) {
            if (!maxHeap.isEmpty()) {
                int maxWork = maxHeap.poll();
                if (maxWork > 0) {
                    maxHeap.add(maxWork - 1);
                }
            }
        }

        long answer = 0;
        while (!maxHeap.isEmpty()) {
            int work = maxHeap.poll();
            answer += (long) work * work;
        }

        return answer;
    }
}

 

 

[Rewind]

1. 어려웠던 점

- 최대 힙을 활용하는 문제 해결 방법을 떠올리는 것이 어려웠다.

 

2. 알게된 점

- 최대 힙을 구현한 후, 정렬되지 않은 무작위 데이터를 삽입할 경우, 자동으로 정렬된다는 것을 알게 되었다.

 

3. 개선 방안

- 여러가지 자료 구조에 대해 알아야 한다고 생각한다.