프로그래머스 - 가장 큰 수

프로그래머스 - 가장 큰 수

숫자로 된 수열을 주고 해당 수열을 조합하여 만들 수 있는 가장 큰 수를 구하는 문제였다.

처음에는 dfs를 이용하여 완전 탐색으로 문제 풀이를 시도하였다. 모든 값들을 조합해보고 모든 수열을 다 썼으면 그 숫자를 string에서 long long으로 변환 후에 vector에 집어넣었다. 그리고 sort를 이용해서 정렬 후 가장 큰 값을 찾아내었다. 문제 설명에서 주어진 테스트케이스가 모두 해결되기에 완료한 줄 알았다. 하지만 시간 초과를 받게 되었다.

이 문제는 dfs를 이용하여 완전 탐색을 해서 푸는 문제가 아니었다. 애초에 문제도 string으로 결과를 받는 만큼 string 형태로만 문제를 해결하면 됬다. 모든 숫자를 string으로 바꿔서 vector에 저장 후에 정렬 조건을 정의해주면 된다. 이때 정렬 조건이 문제를 푸는 핵심이었다. string을 합쳤을 때 최대가 되는 것을 조건으로 vector를 정렬하는 것이었다. 매우 신박한 방식이라 감탄을 했다. 그 후에는 그냥 출력만 해주면 된다. 이때 모든 것이 0인 수열이 주어질 수 있기에 맨 앞이 0일 경우에는 그냥 0만 답으로 출력해주면 된다.

완전 탐색을 많이 연습하여 그 능력치는 오른 것 같지만 너무 무턱대고 완전 탐색만 시도해보려는 경향이 있는 것 같다. 좀 더 문제를 다양한 방면에서 볼 수 있는 시야를 키워야할 것 같다.

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

using namespace std;

vector<string> v;

// 정렬 조건
bool compare(string a, string b) {
    return a + b > b + a;
}

string solution(vector<int> numbers) {
    string answer = "";
    for (auto el : numbers) {
        v.push_back(to_string(el));
    }
    sort(v.begin(), v.end(), compare);
    for (auto el : v) {
        answer += el;
    }
    if (answer[0] == '0') { // 수열의 모든 값이 0일 경우
        return "0";
    }
    return answer;
}

int main() {
    vector<int> numbers;
    numbers.push_back(6);
    numbers.push_back(2);
    numbers.push_back(10);

    string answer = solution(numbers);
    cout << answer << endl;
    return 0;
}