[PG / C++] 프로그래머스 가장 큰 수

문제

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

 

---

풀이

처음에는 브루트포스로 풀려고 했으나, 시간 초과가 나왔다.

1. 수를 문자열로 바꾸고, 벡터에 저장한다.

2. 문자열을 더했을 때 큰 값이 앞에 가도록 (오름차순) cmp 함수를 만들었다.

3. 이후 벡터를 돌면서 문자열을 더하고, 최댓값이 0인 경우 000 같은 값이 나올 수 있기에 예외처리를 추가했다. 

#include <bits/stdc++.h>

using namespace std;

string ans = "";
bool cmp(string a, string b) { 
    return a + b > b + a; 
}
string solution(vector<int> numbers) {
    vector<string> v;

    for (auto n : numbers) {
        v.push_back(to_string(n));
    }
    sort(v.begin(), v.end(), cmp);

    for (auto n : v) {
        ans += n;
    }
    if (ans[0] == '0') {
        return "0";
    }

    return ans;
}