야근 지수(프로그래머스, Lv 3, Java)

1. 야근 지수

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/12927

프로그래머스

알고리즘 설명:

기수 값이 1이라도 높으면 무조건 손해, 따라서 배열 값들을 고르게 만들어주는 작업이 필요하다.

• (큰 순서 기준) 2번째 인덱스부터 자신보다 앞에 있는 인덱스들의 값들을 자신과 같아지게 한다.
• 이때 값을 차이만큼 한꺼번에 빼는 것이 아니라 1씩 차례대로 맨 앞 인덱스부터 빼주어야 한다.
• 맨 앞 인덱스부터 빼주는 이유는 while문을 빠져나가는 조건을 기준 다음 값과 비교하여 결정하기 때문
• cal이라는 메서드는 남은 n값을 배열 크기만큼 나누어 몫(전체에 빼주어야 하는 값)과 나머지 값(차례대로 빼주어야 하는 값)을 배열 값들에 마이너스한 뒤 제곱하여 더한 값들을 누적하여 리턴
• 여기서 배열 전체에 몫을 뺄 때 마이너스 값이 될 수 도 있으므로 조건문으로 값을 0으로 만들어준다.  

막힌 부분:

• n값을 1개씩 뺄 때 인덱스에 차례대로 접근하여 1씩 빼지 않고 한 인덱스에서 한꺼번에 뺐다.
• 한 인덱스에 접근하여 1씩 빼다가 n값이 부족하여 for문이 멈춰버리면 아직 빼지 못한 인덱스 값들 때문에 최솟값이 나오지 않는다.
  • 값을 고르게 만들어야 최소값

코드(Java):

package coding;

import java.util.Arrays;

public class OverTimeIndex {
	public static long solution(int n, int[] works) {
		Arrays.sort(works);

		for (int i = works.length - 2; i >= 0; i--) {
			while (works[i + 1] > works[i]) {
				for (int j = works.length-1; j > i &&n>0; j--) {
					works[j]--;
					n--;
				}
				if (n == 0)
					return cal(works,0,0);
			}
		}

		int idx = n / works.length;
		int rem = n % works.length;
		return

		cal(works, idx, rem);

	}

	public static long cal(int[] works, int minus, int addMinus) {
		long answer = 0;
		for (long work : works) {
			work -= minus;
			if (work < 0)
				work = 0;
			if (addMinus > 0 && work > 0) {
				work--;
				addMinus--;
				answer += (work * work);
			} else
				answer += (work * work);
		}
		return answer;
	}

	public static void main(String[] args) {
		int[] a = { 4, 3, 3 };
		System.out.println(solution(4, a));

	}

}