(Java) 프로그래머스 - 최고의 집합

입력값이 매우 클수도 있기 때문에 효율성 맞추기가 어렵겠다라는 생각이 들었다.

처음에는 재귀를 이용해서 조합을 만드려고 했는데 100% 효율성 테스트에서 걸린다고 생각해서

최대한 간단한 로직으로 풀기위해 고민했다.

조금 생각해보니 금방 로직이 보여서 성공했다.

 

로직

answer 배열의 크기를 n으로 초기화 한다.

for문을 돌면서 answer 배열의 값을 찾는데

s를 cnt로 나눈 temp의 값이 배열의 첫번째 값이다. 

만약 temp가 0이면 모든 원소의 곱은 0이 되기 때문에 바로 배열에 -1를 넣고 반환한다.

temp의 값이 0이 아니면 s에서 temp값을 빼주고 cnt를 줄인다.

이렇게 n번 반복하게 되면 최고의 집합을 찾을수 있다.

---

최종 코드

import java.util.*;
class Solution {
    public int[] solution(int n, int s) {
        
        // 배열의 크기 n으로 초기화
        int[] answer = new int[n];
        
        int cnt = n;
        for (int i = 0; i < n; i++) {
            int temp = s / cnt;
            // 0이 하나라도 있으면 모든 원소의 곱은 0
            if(temp == 0) {
                answer = new int[]{-1};
                return answer;
            }
            answer[i] = temp;
            s -= temp;
            cnt--;
        }
        return answer;
    }
}