프로그래머스: 가장 큰 수 (C++)

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42746

알고리즘 연습 - 가장 큰 수 | 프로그래머스

0 또는 양의 정수를 가지는 배열이 주어질 때, 그것을 나열해서 만들 수 있는 가장 큰 수를 string type으로 반환하는 문제이다.

 

처음에는 단순히 사전식 정렬 이후에, 가장 큰 자릿수의 숫자가 같다면, 길이가 짧은 수가 앞에 와야 큰 수를 만들어낸다고 생각했다.

 

너무 단순한 생각이었다. 비교하고자 하는 숫자의 길이가 다를 경우에 여러 가지 경우를 고려해줘야 한다.

 

그렇다면 비교하고자 하는 숫자의 길이를 같게 만들어주면 된다.

 

45와 4642 중에 어떤 수를 앞에 두어야 올바른 정렬일까 생각해보면,

 

두 수를 두 가지 방법으로 붙여서 454642와 464245를 비교하면 되는 것이다.

 

 

#include <string>
#include <vector>
#include<bits/stdc++.h>

using namespace std;
bool cmp(string a, string b){
    //a가 b보다 먼저 나오는 경우가 true
    if(a + b > b + a)
        return true;
    else
        return false;
}
string solution(vector<int> numbers) {
    string answer = "";
    
    //길이가 다른 경우가 문제니까 길이를 같게 해주려면?
    //비교하는 수 두개를 순서를 바꿔가면서 이어서 붙여보면됨.
    //길이만 같으면 사전순 비교나 크기 비교나 똑같으니까
    
    vector<string> v;
    for(int i = 0 ; i < numbers.size() ; i++)
        v.push_back(to_string(numbers[i]));    
    sort(v.begin(), v.end(), cmp);
    
    //전부 0일 수도 있나?
    bool allZero = true;
    
    for(int i = 0 ; i < v.size() ; i++){
        answer += v[i];
        if(v[i] != "0") allZero = false;
    }
    if(allZero)
        return "0";
    else
        return answer;
    
}