연습문제 : 최고의 집합 ( 프로그래머스 / java )

*해결 과정

 처음에는 이 문제를 중복 조합으로 접근하였습니다. 혹시 문제가 해결되지 않은 상태에서 이 글을 보신다면 간단하게 접근하여 다시 생각히시기 바랍니다. 아래 간단한 테스트 케이스도 첨부합니다. 힌트는 최대한 공평하게 수를 분배하는 것입니다!! 저도 갈피를 잡지 못해 다른 글을 참고하였고 다시 풀어서 맞았습니다. 참고로 효율성도 요구하는 문제이기 때문에 O(N)시간에 처리가 가능해야 합니다.

 

*테스트케이스

n = 3  / s = 8 / 답 [2,3,3]

n = 3  / s = 7 / 답 [2,2,3]

n = 4  / s = 14 / 답 [3,3,4,4]   

 

 

 나머지가 있는 경우, 없는 경우 등등 많은 경우들을 나누어서 풀어보았습니다. 그렇게 조건을 걸어서 풀었더니, 제대로 풀리지 않았고 재귀를 생각하였습니다. 특히 테스트케이스를 만들어서 다양한 상황을 고려했습니다. 테스트 케이스를 만드는 것도 실력이니 자신의 코드를 검증할 다양한 방법을 고민해 보시기 바랍니다. 전에 말씀드렸던대로, 아주 큰 숫자, 아주 작은 숫자, 한쪽으로 쏠린 경우 등등 다양한 예외상황을 생각하시면 됩니다. 

 

그렇게 저는 현재 n의 숫자를 계속 사용하지 않고 연산을 하면서 n을 줄여나갔습니다. 코드를 통해 확인하시겠습니다.

 

import java.util.*;
class Solution {
    public int[] solution(int n, int s) {
        if(n>s) return new int[]{-1};
        
        int[] answer = new int[n];
        int p = s;
        int q = n;
        for(int i=0;i<n;i++){
            
            answer[i] = p/q;
            p -= p/q;
            q--;
            
        }
        Arrays.sort(answer);
        return answer;
    }
}