[알고리즘 문제] 16496번 큰 수 만들기

1. 문제 설명

N개의 숫자들이 주어진다. 이 숫자를 적절히 나열하여 한 개의 수를 만들 때 최대가 되도록 만들어라. 단, 맨 앞의 수가 0이 될 수는 없으며 그러한 경우 0을 출력해라. N은 1000이하의 자연수이다.

 

16496번: 큰 수 만들기

출처 : https://www.acmicpc.net/problem/16496

 

2. 풀이

1) 접근 과정

처음에 보자마자 그냥 그리디로 풀면 되겠다고 떠올렸다... 그렇게 생각한 까닭은 "정렬" 이라는 키워드가 보였기 때문이다. 그리고 숫자들을 변형시키는 것 또한 아니고 숫자를 크게 만든다는 행위는 앞의 자리 수가 가장 크게 되도록 배치만 하면 되기 때문에 그리디의 냄새를 심하게 풍겼다. 

 

그렇다면 앞의 자리 수가 가장 크게 배치 하기 위해서 어떻게 비교할 수 있을까? 입력으로 주어진 수에 대하여 i번째 수가 j번째 수보다 앞에 오는 경우, 뒤에 오는 경우 어떤 경우의 수가 더 큰지 비교만 해주면 된다. 그리고 수를 오른쪽, 왼쪽으로 배치하는 과정을 쉽게 만들기 위해 string을 이용했다. 함수 중에는 stoll, atoll도 있지만 오류가 뜰 수도 있기에 직접 구현했다. 물론 comp과정을 구현할 수 있기에 sort를 사용하는 코드가 더 좋다.

 

처음에 for문을 사용해서 풀었는데 그 까닭은 수를 정렬하라 생각했긴 했지만 그것 보다는 최선의 수를 "선택" 한다가 쫌 더 친숙하여 i번 수행하여 매번 최댓값을 구하는 코드를 짰는데.. 나중에 보니 그냥 정렬하면 되는 것을 살짝 뒤늦게 깨달았다.

 

2) 코드 - MN²

#include <bits/stdc++.h>
using namespace std;

int N, chk[1005];
string num[1005];
vector<int> v;

long long int get_num(string n)
{
    long long int value = 0;
    for(auto&i:n) value = value * 10 + i;
    return value;
}

bool comp(int a, int b)
{
    if(!num[a][0]&&!num[b][0]) return 1;
    return get_num(num[a] + num[b]) < get_num(num[b] + num[a]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> num[i];
    num[0] = "0";

    for(int i=1; i<=N; i++){
        int m = 0;
        for(int j=1; j<=N; j++){
            if(chk[j]) continue;
            if(comp(m, j))
                m = j;
        }
        if(i==1&&!m){cout<<0; return 0;}
        chk[m] = 1;
        v.push_back(m);
    }
    for(auto&i:v) cout << num[i];
}

 

3) 코드 - MNlogN

#include <bits/stdc++.h>
using namespace std;

int N;
string num[1005];

long long int get_num(string n)
{
    long long int value = 0;
    for(auto&i:n) value = value * 10 + i;
    return value;
}

bool comp(string&a, string&b)
{
    if(!a[0]&&!b[0]) return 1;
    return get_num(a + b) > get_num(b + a);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N;
    for(int i=0; i<N; i++) cin >> num[i];
    sort(num, num+N,comp);
    if(num[0] == "0") cout << 0;
    else for(auto&i:num) cout << i;
}

 

 

맨 아래의 경우 stoll함수가 범위를 벗어나 오류 코드를 발생시켰다. atoll을 사용 시 오류 코드가 발생하지 않아 맞는다고 한다. 그리고 2번째는 2중 for문을 사용해서 푼 결과고 맨 위의 코드는 sort를 이용했다. 

 

3. 소감

문제가 크게 어렵진 않았지만 이 문제를 통해 그리디의 전형적인 느낌을 받을 수 있었다. 그리고 저런 문제를 풀 때 

 

최선의 수를 "선 택" 해야한다.

                         

 라고 생각하여 "선택"에 포커스에 맞추다보니 2중 for를 사용했는데 이 선택을 효율적으로 sort를 사용하여 나타낼 수 있다는 것을 느끼고 경험할 수 있었다. 처음 풀었을 때 실망했던 문제였지만 그래도 나름의 깨달은 것이 있으니.. 나쁜 문제는 아니었다. 

 

근데 이게 대체 왜 플5일까...