[프로그래머스/Lv. 3] 최고의 집합(JAVA)

📖 문제

프로그래머스

 

 

💡  풀이 방식

• 그리디

최고의 집합
: 집합을 구성하는 숫자들 간 차이가 가장 작은 케이스

 

1. s를 n으로 나눈 몫으로 배열의 모든 값을 초기화한다.

2. 뒤쪽에서부터 s를 n으로 나눈 나머지를 배열에 1씩 나눈다.

(뒤쪽에서부터 해야 오름차순 정렬 효과 가질 수 있음)

 

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public int[] solution(int n, int s) {
        if(n > s) {
            return new int[]{-1};
        }
        
        int[] answer = new int[n];
        for(int i = 0 ; i < n ; i++) {
            answer[i] = s / n;  // 몫으로 모든 칸 초기화
        }
        
        // 마지막 요소부터 1씩 증가 (오름차순 정렬 위해)
        int remain = s % n;
        for(int i = n - 1 ; i >= n - remain ; i--) {
            answer[i]++;
        }
        
        return answer;
    }
}

 

 

 

➕ 다른 풀이 방식

완전 상세한 설명,,, 최고

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

 

---

💦 어려웠던 점

- '숫자들 간 차이가 작아야 최고 집합을 구성할 수 있다'는 아이디어는 캐치했는데 얘를 어찌 구해야 할지는 몰랐다,,

- dp문제인가 하고 삽질을 열심히 했다,,^^

 

 

🧐 새로 알게 된 내용

- 일단 배열에 몫을 모두 넣어두고, 나머지를 각 원소에 분배해서 1씩 더해주는 아이디어 !

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[연습문제] 최고의 집합 - JAVA