[프로그래머스] 12938. 최고의 집합 C++ / Python 풀이

코딩테스트 연습 → 연습문제 → Lv. 3 최고의 집합

 

풀이 방법

결론부터 말하자면 그리디(Greedy) 기법을 사용해야 한다. 집합 내 필요한 원소의 개수 n개가 있을 때, 각각의 원소에 s 값이 골고루 분배 되어야 한다. 즉, 차이가 가장 덜 나는 원소들로 집합을 이루어야 한다는 것이다. 말로 설명하자면 어려우니 예시와 함께 이해해보자.

 

n = 2, s = 9일 때를 보자. 현재 집합에 아무 숫자도 넣지 않았기 때문에 필요한 원소의 개수는 2개이다. 이는 [1, 8], [2, 7], [3, 6], [4, 5]와 같이 분배가 될 수 있는데 각 원소의 차이가 가장 적은 원소 집합은 [4, 5]이다. 그러므로 정답이 [4, 5]가 되는 것이다.

 

위의 예시만으로는 감이 잡히지 않을 것이다. 다른 예시로 n = 4, s = 10일 때를 보자. [1, 1, 1, 7], [1, 2, 3, 4], ... 10을 4개의 원소로 나누기만 해도 너무 많은 집합들이 나오므로 완전탐색은 비효율적이라는 것을 알아야 한다. 그렇다면 이 상황에서 최고의 집합은 무엇일까? 각각의 원소 간 차이가 가장 덜 나는 [2, 2, 3, 3]이 정답일 것이다.

예시를 보고 (큰 숫자 × 작은 숫자)보다 (중간 숫자 × 중간 숫자)의 연산값이 더 크다는 것을 깨달아야 풀 수 있는 문제이다.

 

구현 방식

풀이 방법은 알았으니, 이제 이를 코드로 구현해야 할 차례이다. 두 번째 예시의 [2, 2, 3, 3]은 머릿 속으로는 쉽게 분배가 가능하지만 구현하려니 [2, 2] 부분이 거슬린다. 필자는 이를 그리디 방식으로 풀었다. 현재 처해있는 상황에서 가장 최적의 값을 도출하는 방식이다.

 

🍀 현재 집합 : [0, 0, 0, 0]

🍀 남은 숫자: 10

std = (int) s / n

먼저, 기준 값을 잡는다. 현재 분배해야 할 숫자는 10, 집합 내 빈 원소 공간은 4이다. 10을 4개의 공간에 분배하는 최적의 숫자는 2.5이다. 우린 정수를 담을 것이기 때문에 소숫점 아래 숫자들은 버려주고 기준 값은 2가 된다. 이 2를 집합의 원소 공간 하나에만 담아줄 것이다.

 

🍀 현재 집합 : [2, 0, 0, 0]

🍀 남은 숫자: 8

2를 원소 공간에 담아주면 분배해야 할 숫자는 8, 집합 내 빈 원소 공간은 3이 된다. 또 현재 상태에서 공간에 값을 분배하는 최적의 숫자를 위와 같은 기준 값 계산 방법으로 찾아준다. 8 ÷ 3 = 2.666... 소숫점 아래 숫자를 버리면 2가 되므로 또 원소 공간 하나에 구한 값을 담아준다.

 

🍀 현재 집합 : [2, 2, 0, 0]

🍀 남은 숫자: 6

이제 남은 숫자는 6, 원소 공간은 2가 되었다. 이는 굳이 계산하지 않아도 [3, 3]이 담긴다는 것을 알 수 있을 것이다. 마찬가지로 위와 같은 방법으로 6 / 2 = 3, 3 / 1 = 3 숫자를 각각 담아주면 최고의 조합이 완성 된다.

 

정답 코드

1. C++

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) {
    vector<int> answer;
    if(s < n) {
        answer.push_back(-1);
    } else {
        int std;
        while(0 < s) {
            std = s / n--;
            answer.push_back(std);
            s -= std;
        }
    }
    return answer;
}

 

2. Python

def solution(n, s):
    answer = []
    while s > 0:
        std = s // n #기준점이 되는 수
        answer.append(std)
        s -= std
        n -= 1
    return answer if min(answer) > 0 else [-1]