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

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

프로그래머스

---

문제

• 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.
• 각 원소의 합이 S가 되는 수의 집합
• 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합
• 예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다.
• { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }
• 그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다.
• 집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요.

제한사항

• 최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 return 해주세요.
• 만약 최고의 집합이 존재하지 않는 경우에 크기가 1인 1차원 배열(list, vector) 에 -1 을 채워서 return 해주세요.
• 자연수의 개수 n은 1 이상 10,000 이하의 자연수입니다.
• 모든 원소들의 합 s는 1 이상, 100,000,000 이하의 자연수입니다.

입출력 예제

설계과정

1. n이 s보다 큰 경우에는 최고의 집합을 만들 수 없으므로 -1을 리턴한다.

 

2. 그 외에 경우에는 배열 answer에 모든 값에 s/n 을 저장한다.

• 예시를 통해 s를 n으로 나눈 수보다 작으면 최대 곱이 되지 않는다는 규칙을 알 수 있다.

3. 그 후 s%n 만큼 answer 배열에 모든 값을 1씩 증가시킨다.

• s가 n으로 나누어 떨어지지 않을 경우에 나머지 만큼을 answer 배열에 뒷부분부터 1씩 더한다.
• ex) 11일때 나머지가 2이므로 answer 배열은 {3, 4, 4}

 

아래 블로그 글을 참조했다.

(혼자서도 막힘없이 풀 날이 언제쯤 올까...)

https://zzang9ha.tistory.com/195

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

https://tosuccess.tistory.com/76

[프로그래머스 level_3] 최고의 집합 for JAVA

---

풀이과정

1. n이 s보다 크면 answer 배열에 값을 모두 -1로 넣는다.

• 예를 들어 n이 10이고, s가 2이면 조건에 해당하는 집합이 존재할 수 없다.

2. 위의 조건이 아니라면 answer 배열에 값들을 모두 s/n 으로 넣는다.

• 예시를 통해 s를 n으로 나눈 수보다 작으면 최대 곱이 되지 않는다는 규칙을 알 수 있다.

3. 그 후에 s%n 만큼 answer 배열에서 1씩 값을 증가시킨다.

• s가 n으로 나누어 떨어지지 않을 경우에 나머지 만큼을 answer 배열에 뒷부분부터 1씩 더한다.

4. Arrays.sort() 를 사용해서 오름차순으로 정렬한다.

 

5. answer 를 리턴한다.

---

답안소스

• 프로그래머스

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<answer.length; i++) {
            answer[i] = s/n;
        }
        for(int i=0; i<s%n; i++) {
            answer[i]++;
        }
		
		Arrays.sort(answer);
        return answer;
    }
}

---

• 이클립스

이클립스의 경우 '-1' 리턴을 위해 answer 배열에 -1을 채우는 조건을 조금 변경하여 작성했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BestSet set = new BestSet();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int s = Integer.parseInt(st.nextToken());
		int[] answer = new int[n];
		
		if(n > s) {
			for(int i=0; i<n; i++) {
				System.out.println(-1);
				return;
			}
		} else {
			for(int i=0; i<answer.length; i++) {
				answer[i] = s/n;
			}
			for(int i=0; i<s%n; i++) {
				answer[i]++;
			}
		}
		
		Arrays.sort(answer);
		
		for(int i=0; i<answer.length; i++) {
			System.out.print(answer[i] + " ");
		}
	}
}