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

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

코딩테스트 연습 - 야근 지수 | 프로그래머스

틀린 코드

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        int sum = 0;
        for(int i=0; i<works.length; i++)
			sum += works[i];
		
		// 작업량 보다 퇴근까지 남은 시간이 더 많은경우
		if(n >= sum) 
			return 0;
		
		while(n != 0) {
			Arrays.sort(works);
			works[works.length-1] --;
			n --;
		}
		
		for(int i=0; i<works.length; i++) {
			answer += (works[i] * works[i]);
		}
        return answer;
    }
}

풀이

 

문제에서 주어진 대로 그대로 접근해서 풀었다.

남은 N시간 동안 작업량 works을 하고, 야근 피로도를 최소화한 값을 리턴하라.

예제 3번과 같이 works = [1,1] , N = 3 일때,

works의 합보다 N이 크거나 같으면 => 모든 작업량을 마쳤으므로 피로도는 0이다.

그 외에는 배열을 정렬한 후 가장 큰값들을 줄이면 야근을 최소화 할 수 있다.

따라서 N이 0이 될때까지, 배열을 정렬하고 가장 큰 값을 줄이는 식으로 했으나 ,,

정확성은 모두 통과했지만 효율성에서 시간초과가 발생했다.

works 의 최대 길이는 20,000 이고 n은 1,000,000 이다.

1,000,000 * 20,000 의 큰 숫자때문에 시간 초과가 발생하는 것 같다.

그래서 접근을 다르게 했다 .

위와 같은 방식대로라면,, 예를들어 작업량이 [1000, 1000, 1000, 1000, 2, 3, ... ] 와 같더라도

작업량이 가장 큰 1000은 여러개이지만, 한번에 한 개밖에 감소시키지 못하므로 비효율적이다.

따라서 works배열에서 최댓값을 찾고, 최댓값과 동일할 때 한번에 감소시키도록 해봤다.

(즉, n을 빠르게 줄일 수 있는 방법에 대해 생각해 보았다.)

 

그러자 효율성에서도 통과가 됐다. 기타 설명은 주석문 , ,

	class Solution {
		public long solution(int n, int[] works) {
			long answer = 0;
			int sum = 0;
			for(int i=0; i<works.length; i++)
				sum += works[i];

			// 작업량 보다 퇴근까지 남은 시간이 더 많은경우
			if(n >= sum) 
				return 0;

			// 남은 시간 만큼 작업량 감소하기
			while(n != 0) {
				int max = 0;

				// 현재 배열 중 작업량이 가장 큰 수 찾기
				for(int i=0; i<works.length; i++) 
					if(works[i] > max)	max = works[i];

				// 배열 요소중 max 값과 동일하면 전부 다 감소시키기
				for(int i=0; i<works.length; i++) {
					if(works[i] == max) {
						works[i] --;
						n --;
						// n이 0일시 => 더이상 감소시키지 말고 종료
						if(n == 0)	break;
					}
				}
			}

			// 남은 작업량 제곱해서 모두 더하기
			for(int i=0; i<works.length; i++) {
				answer += (works[i] * works[i]);
			}

			return answer;
		}
	}