[프로그래머스] 야근지수 (Java, Level.3)

문제

1. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값

2. N시간 동안 야근 피로도를 최소화하도록 일할 것.

3. 1시간 동안 작업량 1만큼을 처리 가능

 

퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 최소 야근 피로도 구하기 

 

 

입출력 예 

풀이

많은 풀이들을 살펴보았다. 

해당 풀이에 대한 분석을 한 결과, 큰수를 작은수가 되도록 하는것이 관건이었다. 

더군다나 남은 일에 대한 제곱을 하기 때문에 일의 개수보다는 가장 큰 작업량을 줄이는 것이 중요하다. 

 

따라서 우선순위 큐를 사용하였다. 

 

1. 우선순위 큐

: 들어간 순서에 상관없이 일정한 규칙에 따라 우선순위 설정 후, 우선순위가 가장 높은 데이터가 먼저 출력

 

 

큐 사용법에 대해서는 해당 게시글을 보면서 공부하였다. 

https://cocoon1787.tistory.com/774

[JAVA] Queue(큐) 사용법 (add vs offer / remove vs poll / element vs peek)

 

2. n시간동안 일을 처리하는 로직

1. 가장 큰값을 가져와 양수가 아닌지 확인

-> 값을 가져올때, 큐에서는 해당 값 제거

 

2. 양수일 경우 -1 한 후에 추가

-> 우선순위 큐를 사용했기에, 자동 내림차순 정렬 따라서 다음에도 가장 큰값을 가져올 수 있다. 

 

3. 양수가 아닐 경우, 일 종료 

 

 

3. 최솟값 

while문을 사용하여 구하였다. 

큐가 빈값이 될때까지 반복하였다. 

 

size 함수를 사용하여 For문을 돌리지 않은 이유는 계속 size가 변하기 때문이다. 

 

최종  코드

public static long solution(int n, int[] works) {

        System.out.println("야근 지수");

        // 큰수를 줄이는게 관건인 문제

        long answer = 0;

        // 1. 우선순위 큐 선언 -> 항상 내림차순으로 정렬할 수 있도록 하기위해 사용

        PriorityQueue<Integer> workQueue = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < works.length; i++) {

            workQueue.offer(works[i]);

        }

        // 2. n시간동안 일처리하기. 가장 큰 일(최댓값)에 대해 -1

        // 2-1. 최댓값0이거나 그보다 작을 경우, 일이 끝났기때문에 0 반환

        for (int i = 0; i < n; i++) {

            int num = workQueue.poll();

            if (num <= 0)

                break;

            else

                workQueue.offer(num - 1);

        }

        // 3. 남은일 제곱

        while (!workQueue.isEmpty()) { // 큐가 비어 있을 때까지

            int work = workQueue.poll();

            answer += Math.pow(work, 2);

        }

        return answer;

    }

 

 

프로그래머스 문제 

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

프로그래머스