프로그래머스 - 야근 지수 문제 (자바)

programmers.co.kr/learn/courses/30/lessons/12927

코딩테스트 연습 - 야근 지수

이 문제는 우선순위 큐를 통해서 가장 큰값 -1를 n 만큼 반복해서 풀수 있다.

다만 이경우 n만큼 반복하게 된다.

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

class Solution {
    public long solution(int n, int[] works) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (int work : works) {
            pq.offer(work);
        }
        
        for (int i = 0; i < n; i++) {
            int max = pq.poll();
            if (max <= 0) break;
            pq.offer(max - 1);
        }
        
        long answer = 0;
        while (!pq.isEmpty()) {
            answer += Math.pow(pq.poll(), 2);
        }
        return answer;
    } 
}

 

밑에 코드는 우선순위 큐에 -1씩하는 방식이 아닌 가장 큰값에서 그다음 큰 값보다 1 작게 만드는 방식이다.

이때 고려해야하는 것은

1. 배열이 2이상인지

2. 둘의 차이가 n보다 큰 경우

 

돌려보니 시간차이가 거의 없긴 하다 .....

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

class Solution {
    public long solution(int n, int[] works) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (int work : works) {
            pq.offer(work);
        }
        
        while(n > 0) {
            int max = pq.poll();
            if(!pq.isEmpty()) {
                int second = pq.peek();
                int temp = max - second + 1;
                int min = temp > n ? n : temp;
                pq.offer(max - min);
                n -= min;
            }else {
                pq.offer(max - n);
                n = 0;
            }
            
        }
        
        long answer = 0;
        while (!pq.isEmpty()) {
            int max = pq.poll();
            if(max > 0) {
                answer += Math.pow(max, 2);
            }
        }
        return answer;
    } 
}