[백준] 1422번 숫자의 신

문제

숫자의 신은 여러명이 있지만, 그 중에 자연수의 신은 오세준이다. 오세준은 자연수의 신으로 오래오래 살다가 어느 날 음수의 신과 전쟁을 하게 되었다. 오세준은 음수의 신 이다솜을 이기기위해서 큰 숫자를 만들기로 했다.

오세준은 지금 K개의 자연수를 가지고 있다. 오세준은 K개의 수 중에 정확하게 N개의 수를 뽑아내서 그 수를 붙여서 만들 수 있는 수중에 가장 큰 수를 만들고자 한다. 같은 수를 여러 번 이용해도 된다. 단, 모든 수는 적어도 한 번은 이용되어야 한다.

오세준이 현재 가지고 있는 K개의 수가 주어졌을 때, 이 수를 적어도 한 번 이상 이용해서 만들 수 있는 수 중에 가장 큰 수를 출력하는 프로그램을 작성하시오.

예를 들어 지금 오세준이 2, 3, 7 이라는 3개의 수를 가지고 있고, 4개의 수를 뽑아야 한다면, 7732를 만들면 가장 큰 수가 된다.

입력

첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 작거나 같은 자연수이다. 이 수는 중복되어 들어올 수 있다. 만약 중복되어서 들어오는 경우에는 각 수가 적어도 입력으로 주어진 만큼 이용되어야 한다는 소리다.

출력

N개의 수를 뽑아서 연결해서 만들 수 있는 가장 큰 수를 출력한다.

예제 입력 1

3 3

3

2

7

예제 출력 1

732

 

소스코드

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

bool cmp(string a, string b) {	// 숫자를 문자열로 인식하고 두 문자열을 연결한 a+b와 b+a 중 더 큰 값이 먼저 오도록 한다.
    string s1=a+b;
    string s2=b+a;
    return s1>s2;
}

int main() {
    int k, n;
    int len=0, idx;
    string num;
    vector<string> v;
    string s="";
    
    cin>>k>>n;
    for(int i=0;i<k;i++) {
        cin>>num;
        if(num.length()>len) len=num.length();	// 입력받은 값들 중에 자릿수가 가장 큰 경우의 자릿수를 저장한다.
        v.push_back(num);
    }
    sort(v.begin(), v.end(), cmp);
    if(v[0].length()==len) {	// 내림차순으로 정렬된 v의 첫번째 값의 길이가 len과 같은 경우이다.
        for(int i=k-1;i>0;i--) {
            s=v[i]+s;	// 첫번째 값을 제외한 모든 값들을 순서대로 하나씩 저장한다.
        }
        for(int i=0;i<n-k+1;i++) s=v[0]+s;	// 남은 자리를 첫번째 값으로 모두 채운다.
    } else {	// 내림차순으로 정렬된 v의 첫번째 값의 길이가 len과 같지 않은 경우이다.
        for(int i=1;i<k;i++) {
            if(v[i].length()==len) {	// v의 값들 중 len과 길이가 같은 값이 처음으로 등장할 때의 인덱스 값을 저장한다.
                idx=i;
                break;
            }
        }
        v.insert(v.begin()+idx, n-k, v[idx]);	// 위에서 찾은 인덱스에 해당하는 값을 n-k번(모든 v값을 한번씩 사용하고 남은 횟수) 인덱스의 위치에 추가한다.
        for(int i=v.size()-1;i>=0;i--) {	// v의 값들을 순서대로 s에 저장한다.
            s=v[i]+s;
        }
    }
    cout<<s<<endl;
    
    return 0;
}

숫자를 문자열로 취급하여 정렬해줄 때, 자릿수가 더 큰 경우를 고려하는 것이 관건인 문제였습니다.

추가로 생각해볼 반례로는 아래와 같은 것들이 있습니다.

예제 입력 2

1 1

4

 

예제 출력 2

4

예제 입력 3

2 3

991

99

예제 출력 3

99991991

예제 입력 4

2 3

889

89

예제 출력 4

89889889

예제 입력 5

2 3

882

83

예제 출력 5

88288283