LV3 최고의 집합 (Java)

 

---

 

문제

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

프로그래머스

풀이

우선, 어떤 상황에 -1이 나올까?

 

n이 3인데 s가 2라고 해보자.

각 원소는 1이상의 값을 가지는데, 최소 형태인 [1, 1, 1] 로 만들면 이미 s를 넘기 때문에 답을 낼 수 없다. 따라서 이때 우선 -1을 담은 배열을 return 하면 된다.

 

그게 아닐경우에는 어떻게 할까?

 

예시를 보면 

n=2, s=9 => [4, 5]

n=2, s=8 => [4, 4]

와 같이 나타난다.

 

이걸 보고 큰 값을 나타내기 위해서는 배열 요소들의 밸런스가 맞아야 한다고 생각했다. (요소간의 차가 거의 없어야 함)

9를 최대한 밸런스 있게 나누면 4와 5이고

8을 최대한 밸런스 있게 나누면 4와 4다. 

 

이렇게 값을 세팅하기 위해서는 우선 s를 n으로 나눠야 한다.

n=2, s=8 => [4, 4] 예제를 보면 8을 2로 나누면 밸런스 있게 4로 세팅된다.

위 예시는 딱 떨이지니까 상관 없는데, 문제는 딱 떨어지지 않는 경우다.

 

n=3, s=5 => [1, 2, 2] 일 때를 보자

 

우선 5를 3으로 나누면 1이 나오고 배열에 [1, 1, 1] 로 세팅 될 거다.

그러면 나머지인 2의 여분값이 생기는데,

오름차순 정렬을 해야하니 뒤에서부터 하나씩 채워주면 된다!

[1, 1, 1] => [1, 1, 2] => [1, 2, 2]

 

 

코드

import java.util.*;

// n개의 원소들 각각의 합으로 s를 만들어야 한다.

class Solution {
    public int[] solution(int n, int s) {
        
        if(n > s) return new int[]{-1};
        
        int[] answer = new int[n];
        Arrays.fill(answer, s/n);
        int mod = s%n;
        while(mod!=0){
            answer[--n]++;
            mod--;
        }
        
        return answer;
    }
}

 

후기

 

처음에는 분기를 홀/짝수로만 뒀다가 나머지가 2이상 나오는걸 간과해서 틀렸다.

 

테스트 케이스 좀 더 작성해보고 제출하자!