프로그래머스 문제 - 가장 큰 수

프로그래머스 가장 큰 수 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

0 또는 양의 정수가 배열로 주어집니다.
주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
이런식으로 가장 큰 정수를 문자열로 변환시켜 return해야 합니다.

문제 풀이

간단해보이면서도 생각해야 하는 부분이 많습니다.
주어진 정수들을 가지고 가장 큰 수를 만들기 위해 숫자가 큰 것부터 사전순으로 정렬한 후 이어붙이기만 하면 가장 큰 수를 찾을 수 있습니다.

쉽게 정렬하는 방법은 a와 b의 수가 있다면 문자열로 변환시켜 a+b와 b+a로 붙인 후 어느 쪽이 더 큰지 확인해주면 됩니다.
이 때 주의해야 하는 점은 두 수를 붙일 때 앞에 0이 오는 경우가 만들어질 수 있는데 이는 수로 표현이 불가능하므로 제외시켜주면 됩니다.

이후 모든 숫자가 0으로 되어있는지 판별 후 만들어진 문자열을 return해주면 됩니다.

전체 코드

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

using namespace std;

bool compare(string a, string b)
{
    //수가 같다면 정렬할 필요 없음
    if(a == b)
        return true;
    
    string str1 = a + b;
    string str2 = b + a;
    
    //맨 앞에 있는 수가 0인 경우는 제외시킴
    if(str1[0] == '0')
        return false;
    else if(str2[0] == '0')
        return true;
    
    int num1, num2;
    
    num1 = stoi(a + b);
    num2 = stoi(b + a);
    
    //내림차순으로 정렬
    return num1 > num2;
}

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> vec;
    
    for(int n : numbers)
    {
        vec.push_back(to_string(n));
    }
    
    sort(vec.begin(), vec.end(), compare);
    
    for(string s : vec)
    {
        answer = answer + s;
    }
    
    //배열 내에 0밖에 없다면 정답은 0
    return answer[0] == '0' ? "0" : answer;
}

출저

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