백준 1422번 숫자의 신

http://icpc.me/1422

1422번: 숫자의 신

풀이

뒤에서 설명할 비교 연산을 편하게 하기 위해 n개의 수를 문자열 자료형으로 받습니다.

 

k개의 수 중 가장 길이가 길고 큰 수를 최대한 많이 반복하는 것이 이득입니다. 따라서 길이순(길이가 같다면 크기순)으로 정렬하여 n - k번 반복할 수를 먼저 선택하고, 정답을 나타낼 벡터에 선택한 수를 n - k번 넣고 k개의 수를 모두 하나씩 넣습니다. 이후 선택한 n개의 수로 가장 큰 수를 만들 수 있도록 벡터를 정렬해야 합니다. 문자열으로 수를 받았으므로 정렬 함수를 아래처럼 짜면 가장 큰 수를 만들 수 있습니다.

 

bool cc(string a, string b) {
    return a + b > b + a;
}

 

정렬된 벡터의 값을 공백이나 줄바꿈 없이 순서대로 출력하면 정답이 됩니다.

 

코드

cmp는 반복할 수를 찾기 위한 정렬 함수이고, cc는 가장 큰 수를 만들기 위한 정렬 함수입니다.

 

#include <bits/stdc++.h>
using namespace std;
bool cmp(string a, string b) {
    if (a.length() != b.length())
        return a.length() > b.length();
    return a > b;
}
bool cc(string a, string b) {
    return a + b > b + a;
}
 
int main() {
    string now;
    vector<string> nums, ans;
    int n, k;
    cin >> k >> n;
    for (int i = 0; i < k; i++) {
        cin >> now;
        nums.push_back(now);
    }
    sort(nums.begin(), nums.end(), cmp);
    for (int i = k; i < n; i++)
        ans.push_back(nums.front());
    for (string i : nums)
        ans.push_back(i);
    sort(ans.begin(), ans.end(), cc);
    for (string i : ans)
        cout << i;
    return 0;
}

비슷한 문제

https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수

가장 큰 수가 되도록 n개의 정수를 재배열하는 문제입니다. to_string등을 통해 받은 정수를 모두 문자열로 바꾸어 벡터에 넣은 뒤 위에서 설명한 함수 cc를 이용하여 정렬하면 답을 구할 수 있습니다. 이 문제를 먼저 풀어서 그런지 플레치고 쉽게 느껴졌습니다.