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

https://school.programmers.co.kr/learn/courses/30/lessons/42746?language=cpp

정렬이지만, 조금은 다르다.

원래는 왼쪽 기준으로 맨 처음 숫자를 고려해서 큰 수형식으로 배열하는 방식을 생각하였다.
하지만 이는 코드상으로 구현하니 굉장히 복잡한 형식이기도 하고, 예외 처리 해야 할 것들이 많이 존재하였다.(ex. 자릿수가 같을 때 숫자비교, 다를 때 짧은 것이 먼저올 수도 있지만, 뒤에 오는 숫자들에 따라 긴 것이 먼저 올 수도 있음)

그런 문제점이 존재해 다른 방식으로 이 문제를 풀 수 있었다.

숫자들을 string으로 전환하여 각 숫자를 합쳐보았다.

3 + 57과 57 + 3을 수행하면 각각 357, 573이 된다.
합쳐보았을 때 573이 더 큰 수 이므로 저 두 숫자를 합칠 때 57 + 3로 수행해야 한다.
이를 numbers에 있는 모든 수에 대해 적용해보면 이어봤을 때 큰 수로 배치가 될 것이다.

 

#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

bool compare (const string &a, string &b) {
    if (a + b > b + a)
        return true;
    else
        return false;
}

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> temp;
    
     for (int i = 0; i < numbers.size(); i++) {
        temp.push_back(to_string(numbers.at(i)));
    }
    
    sort(temp.begin(), temp.end(), compare);
    
    for (int i = 0; i < temp.size(); i++) {
        answer += temp.at(i);
    }
    
    if (answer[0] == '0')
        return "0";
    
    return answer;
}

vector<string> temp; 로 미리 to_string을 적용해 저장하지 않고, 각각의 원소에 대해 to_string을 수행하면 몇몇 케이스에서 시간 초과가 발생한다.

또한 특정 케이스(case. 11)에서 000000식으로 저장이 되는 데, 그것을 0으로 저장해야 정답으로 인정된다. 그러므로 하나의 string값에 가장 왼쪽 값(answer[0])을 확인하여 '0'일 경우, "0"으로 리턴시켜주었다.