[C++]백준 1422번: 숫자의 신

문제

https://www.acmicpc.net/problem/1422

1422번: 숫자의 신

 

문제이해

 

• K와 N을 입력한다. (1 ≤ K ≤ N ≤ 50)
• 둘째 줄부터 K개의 수(X)를 한 줄에 하나씩 입력한다. (1 ≤ X ≤ 1,000,000,000)
• N개의 수를 뽑아서 연결해 만들 수 있는 가장 큰 수를 출력한다.

문제를 해결하기 위해서는 수들을 특정 규칙에 따라 정렬해야 한다. 다음의 예시를 보자.

 

199 10

199와 10을 각각 한번 싹만 사용하여 만들 수 있는 수는 19910과 10199이고 이중 큰 수는 19910이다.

 

100 10

100과 10의 경우는 10010과 10100을 만들 수 있고 10100이 더 큰 수가 된다.

 

199 100 19

3개의 숫자를 각각 1개씩 이어 붙이는 경우는 19910019, 19919100, 10019919, 10019199, 19199100, 19100199가 있으며 여기서 가장 큰 수는 19919100이다.

3개의 숫자를 2개씩 묶어서 비교해 보자.

199와 100으로는 199100과 100199를 만들 수 있고 199100이 더 크다.

100과 19로는 10019와 19100을 만들 수 있고 19100이 더 크다.

199와 19로는19919와 19199를 만들 수 있고 19919가 더 크다.

순서로 따지자면 199 -> 19 -> 100 순서로 이어 붙일수록 더 큰 수가 나온다.

 

 

위의 예시들처럼 K개의 숫자를 각각 1번씩만 사용하여 큰 수를 만들기 위해서는 두 수끼리 있어 붙이기를 했을 때 큰 순서나 작은 순서대로 정렬하면 된다.

 

K개의 숫자들을 각각 1번씩만 사용하는 것이 아닌 여러 번 사용하는 경우는 어떨까?

간단하다. 우선순위가 가장 높은 수를 N - K번 있어 붙이면 된다.

 

199 100 19

3개의 숫자를 5번 이용하려고 한다. 이때 만들 수 있는 가장 큰 수는 19919919919100이다. 199가 나와야 할 부분에 199를 N - K번 출력해주기만 하면 된다.

 

다음은 위의 설명대로 만들어진 백준 1422번 숫자의 신 C++ 코드이다.

 

문제풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;

int main() {
    int n, m, x;
    cin >> n >> m;
    vector<int> numbers(n);
    for (int i{ 0 }; i < n; i++) {
        cin >> numbers[i];
    }

    sort(numbers.begin(), numbers.end(), [](int a, int b) {
        string strA = to_string(a);
        string strB = to_string(b);
        return strA + strB > strB + strA;
    });

    int maximumIdx{ 0 };

    for (int i{ 0 }; i < n; i++) {
        if ((static_cast<int>(log10(numbers[i]) + 1) > (static_cast<int>(log10(numbers[maximumIdx])) + 1))) {
            maximumIdx = i;
        }
        else if ((static_cast<int>(log10(numbers[i])) == static_cast<int>(log10(numbers[maximumIdx])))) {
            if (numbers[i] > numbers[maximumIdx]) {
                maximumIdx = i;
            }
        }
    }

    for (int i{ 0 }; i < n; i++) {
        if (i == maximumIdx) {
            for (int a{ 0 }; a <= m - n; a++) {
                cout << numbers[i];
            }
        }
        else
            cout << numbers[i];
    }
}

sort를 이용하여 먼저 나와야 되는 순서대로 vector안의 원소들을 정렬하였다. 이후 우선순위가 가장 높은 원소를 찾고 해당 원소를 N - K번 출력하는 과정을 추가해주기만 했다.

 

 

문제후기

정렬법은 떠올리는데 크게 어렵지 않았으나 어떤 수를 여러 번 어느 곳에 출력해야 되는지 생각해야 되는 문제였다.