가장 큰 수

들어가는 말

int형으로 받은 numbers를 가지고 새로운 숫자를 만들어서 가장 큰 숫자를 출력하는 거다.

문제를 본 순간 순열로 풀면 되겠다고 생각했다. 그래서 next_permutation()을 이용했는데 시간 초과가 나왔다. 그래서 직접 순열 함수를 작성해서 풀었는데 여전히 시간 초과가 나왔다. 아니면 아예 답이 안 나오거나. 어째서! 난 꼭 순열로 풀고 싶었는데... 여튼 순열로 풀겠다고 한 시간 쓰고 그냥 string로 바꿔서 더해서 sort하는 방법을 썼다. 시간 초과만 아니면 순열로 풀 수 있었을 텐데...

코드 설명

numbers가 정수형이므로 일단 문자열로 바꾸어야 한다. 왜냐하면 정수형으로 더하기를 했을 경우 진짜 더하기를 하기 때문이다. 문제가 원하는 건 더하기가 아니라 숫자 그자체를 붙이는 거다. 때문에 numbers들을 string형으로 바꿔서 string형 벡터 s에 넣어준다.

다음에는 주어진 조건대로 sort를 하면 된다. 이때 sort의 기준은 문자열로 더했을 때 더 큰 수다. 예를 들어 a가 6이고 b가 10일때, a+b(610)이 b+a(106)보다 크니 true로 sort가 된다는 거다. 문자열끼리 더해서 비교가 가능하다는 걸 처음 알았다.

그리고 sort한 벡터를 answer에 전부 더해주면 된다. 만일 s가 0이라면 문자열 0을 리턴한다.

코드

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

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

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> s;
    
    for(auto n : numbers){
        s.push_back(to_string(n));
    }
    
    sort(s.begin(), s.end(), cmp);
    
    if(s[0] == "0"){
        return "0";
    }else{
        for(auto s1 : s){
            answer += s1;
        }
    }
    return answer;
}

이건 순열로 구하려다 실패한 코드. 완성하지는 않았다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

void swap(char &a, char &b){
    int tmp = a;
    a = b;
    b = tmp;
}

int permutation(vector<int> numbers, int depth, int n, int r){
    vector<int> num;
    string s = "";
    vector<string> s1;
    vector<int> num1;
    
    for(auto n : numbers){
        num.push_back(n);
    }
    
    if(depth == r){
        for(int i=0; i<r; i++){
            s = s + to_string(num[i]);
        }
        s1.push_back(s);
        s = "";
    }else{
            for(int i = depth; i<n; i++){
            swap(num[depth], num[i]);
            permutation(num, depth+1, n, r);
            swap(num[depth], num[i]);
        }
    }
    
    for(int i=0; i<s1.size(); i++){
        num1.push_back(stoi(s1[i]));
    }
    
    auto max = num1[0];
    cout << max;
    for(auto n : num1){
        cout << n << endl;
    }
    

    return max;
    
    
}
string solution(vector<int> numbers) {
    string answer = ""; 
    int num;
    
    num = permutation(numbers, 0, numbers.size(), numbers.size());

    return answer;
}