[백준] 1422 숫자의 신

1422번: 숫자의 신

문제 확인

 

문자열 혹은 숫자 자릿수를 활용하는 문제입니다.

 

풀이

 

간략한 풀이를 위해 입력을 문자열로 받습니다.

최대의 숫자를 만들기 위해서는 몇 가지를 고려해야 합니다.

1. 맨 앞자리는 1~9 중 재일 높은 수가 나와야 합니다.
2. 모든 수를 고르고 난 후 남은 n-k개의 수는 가장 긴 자릿수 중 재일 높은 수를 선택해야 합니다.

1번을 고려할때 주의해야 할 점은 91, 9 의 경우9/91이 더 높은 숫자를 만들 수 있는 것입니다. 이를 위해 두 숫자 a, b가 있을 때 이들을 a/b : b/a를 비교하여 정렬을 합니다.

c++에서는 string 객체를 통해 간단하게 두 문자열을 비교하고, a/b를 a+b로 구현할 수 있으며 이를 활용해 a+b > b+a로 정렬을 합니다.

 

2번을 고려할 때 입력받을 시 최대 문자열을 찾아가고 모든 입력이 끝나면 남은 개수만큼 배열에 추가로 삽입해주면 됩니다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
 
int main() {
    int n, k;
    cin >> k >> n;
    vector<string> ary(n);
    string mx;
    for (int i = 0; i < k; i++) {
        cin >> ary[i];
        mx = mx.size() < ary[i].size() || (mx.size() == ary[i].size() && mx < ary[i]) ? ary[i] : mx;
    }
    for (int i = k; i < n; i++)
        ary[i] = mx;
 
    sort(ary.begin(), ary.end(), [](string &a, string &b)->bool {
        return a + b > b + a;
    });
 
    for (int i = 0; i < n; i++)
        cout << ary[i];
 
}