[Programmers/Lv.3] 최고의 집합 - Java

알고리즘 문제 풀이 / 프로그래머스 (programmers)  - 최고의 집합

 

▏시작하는 말

오래간만에 프로그래머스 문제를 풀어봤다. 이번 문제는 LV3 단계인게 믿기지 않을만큼 쉽게 풀 수 있었다. 이 문제의 원리만 파악한다면 누구든 쉽게 풀 수 있으리라 생각한다.

 

 

▏문제 설명

자연수 n 개로 이루어진 집합 중 다음 두 조건을 만족하는 집합을 최고의 집합이라고 정의한다. 

    1. 각 원소의 합이 S가 되는 수의 집합

    2. 위 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합

 

n=2, s=9 일 때를 예를 들자면,

조건 1을 만족하는 집합은 { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }이다.

조건 1을 만족하며 조건 2를 만족하는 집합은 { 4, 5 }가 된다.

 

제한사항

   ◦ 집합은 오름차순으로 정렬된 1차원 배열로 return 한다.

   ◦ 집합이 존재하지 않는 경우 배열에 -1을 채워 return 한다.

   ◦ n은 1 이상 10,000 이하의 자연수

   ◦ s는 1 이상 100,000,000 이하의 자연수

 

 

▏문제 풀이

내가 생각했을 때 이 문제의 핵심은 "각 원소의 곱이 최대가 되려면 어떤수를 곱해야 하는가"  이다.

단순하게 생각해보면 어떤 수 들의 곱이 가장 크려면 큰 수들끼리 곱해야 한다.

 

문제 설명부분에서 예시로든  n=2, s=9 의 조건1을 만족하는 집합 { 1, 8 }, { 2, 7 },  { 3, 6 }, { 4, 5 } 을 살펴보자. 

 

얼핏 생각하면, 8이 가장 크니까 1 x 8이 가장 큰게 아닐까? 1은 너무 작으니 중간쯤인 3 x 6 ? 이렇게 생각할 수 있으나 곱셈이 가장 크려면 곱할 모든 수들이 큰게 가장 큰 수가 된다.

 

곱할 모든 수가 크려면 조건 1의 맨 마지막 집합이 결국 가장 큰 수들인 것이다. 또 이말은 s를 n으로 나누었을 때의 몫과 그 나머지를 하나씩 나누어 가진 수가 맨 마지막 집합이 되는 것이다.

 

다시 n=2, s=9 경우를 보자. 

s / n 의 몫은 4 나머지는 1

이 나머지를 하나씩 나누어 가지면 4, 5 가 되는것이다.

 

만약 n=3, s=9 라면

몫은 3 나머지는 0 그럼 답은 { 3, 3, 3 } 이 되는 것이다.

 

 

이런 생각을 거친 후 풀이 순서를 정했다.

 

1. 집합이 존재하지 않는 경우 처리

2. s / n 의 몫과 나머지 변수설정

3. 오름차순 정렬을 해야하므로 n-1 부터 시작하여 answer 입력

 

 

public int[] solution(int n, int s) {
        if(s < n) {
        	int[] none = {-1};
        	return none;
        }
        
    	int[] answer = new int[n];
        
        int quot = s / n;
        int remain = s % n;
               
        for(int i = n-1; i >= 0; i--) {
        	int one = remain-- > 0 ? 1 : 0;
        	answer[i] = quot + one;
        }
        
        return answer;
    }

 

 

 

▏문제 링크

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

프로그래머스