[프로그래머스] Lv.3 최고의 집합.java

lv.3 최고의 집합.java

class Solution {
    public int[] solution(int n, int s) {
        if(n>s){ // 합이 S가 되는 n개의 원소를 가진 집합이 존재하지 않는 경우
            return new int[] {-1};
        }
        int[] answer = new int[n];
        
        if(s%n==0){ //나눠지는 경우
            for(int i=0; i<n; i++){
                answer[i] = s/n; //가능한 작은 수부터 차례로 집합에 추가
            }
        }else{ //안나눠지는 경우
            int remainder = s%n; //나머지를 계산하여 나중에 추가
            int po = n - remainder; //1씩 더해줘야하는 인덱스 위치
            for(int i=0; i<po; i++){
                answer[i] = s/n;//po까지는 원래대로 추가
            }
            for(int i=po; i<n; i++){
                answer[i] = s/n+1;//po부터 n까지는 1씩 추가
            }
        }
        return answer;
    }
}

n과 s를 입력 받아서, s를 n개의 원소로 만드는 집합을 찾는 문제를 해결합니다.

만약에 n이 s보다 크다면, 합이 S가 되는 n개의 원소를 가진 집합이 존재하지 않는 것입니다. 이 경우에는 -1을 리턴합니다.

만약에 s가 n으로 나누어 떨어진다면, 집합의 모든 원소가 같은 값을 가지면서 s를 합으로 갖는 n개의 원소 집합이 존재합니다. 이 경우에는 s를 n으로 나눈 값을 n개의 원소로 갖는 집합을 만듭니다.

그러나 s가 n으로 나누어 떨어지지 않는 경우에는 더 복잡합니다. 이 경우에는 s를 n으로 나눈 몫만큼 집합에 추가하고, 나머지 값이 있는 만큼 1씩 값을 추가합니다. 이를 위해서, 먼저 나머지 값을 계산하고, 나머지 값이 있는 만큼 1씩 값을 추가하기 위한 인덱스 위치를 찾습니다. 그리고 po 위치까지는 몫을 원소로 추가하고, po 이후부터는 1씩 값을 추가합니다.

최종적으로 구한 집합을 리턴합니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges