(Java) 프로그래머스 - 야근 지수

효율성 테스트를 통과하기 어려웠던 문제였다.

최대한 시간 복잡도를 줄여서 코드를 작성하려고 노력했지만

한 번에 통과하진 못하고 여러 가지 로직으로 시도해서 성공했다.

 

로직

첫 번째 시도는 list를 사용해서 최댓값의 인덱스를 찾고 set을 통해 값을 변경하는 로직이었지만

효율성에서 통과하지 못했다. 아마 최댓값의 인덱스를 찾는 과정에서 시간이 꽤 소요돼서 통과하지 못했던 것 같다.

 

두 번째 시도는 매번 배열을 정렬하면서 가장 뒤에 있는 값에 -1 해주며 n을 줄이는 로직으로 시도했지만 이것도 효율성을 통과하지 못했다.

 

마지막 시도는 내림차순 우선순위 큐를 선언하고 큐의 가장 앞에 있는 값을 줄이는 로직으로 성공했다.

---

실패 코드

import java.util.*;
class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < works.length; i++) {
            list.add(works[i]);
        }

        while (n > 0) {
            int idx = list.indexOf(Collections.max(list));
            if (list.get(idx) == 0) {
                break;
            }
            list.set(idx, list.get(idx) - 1);
            n--;
        }

        for (int i = 0; i < list.size(); i++) {
            answer += Math.pow(list.get(i), 2);
        }
        return answer;
    }
}

 

최종 코드

import java.util.*;
class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        // 내림차순 우선순위 큐 선언
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        
        // 큐에 배열값 넣기
        for (int i = 0; i < works.length; i++) {
            queue.add(works[i]);
        }
        
        while (n > 0) {
            // 가장 큰 수가 0이면 탐색중단
            if (queue.peek() == 0) {
                break;
            }
            queue.add(queue.poll() - 1);
            n--;
        }
        
        // 큐에 있는 값 제곱해서 더하기
        while (!queue.isEmpty()) {
            answer += Math.pow(queue.poll(), 2);
        }
        return answer;
    }
}