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

👓 문제 설명

---

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

입출력 예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

---

---

💣 제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

---

🚨 접근 방법

sort에 들어갈 cmp함수를 커스텀하는 문제이다.
처음 풀이 방법으로는 비교할 두 수의 자릿수를 구하고
mod연산을 통한 나머지를 비교하여 정렬하는 방법이었다.
예를들어 3과 34가 있으면 334보다 343이 더 크므로
3<(34%10)을 통해 정렬을 하였다.

하지만 이렇게 코드를 작성하니 일부는 올바르게 정렬 되었으나 일부는 정렬이 되지 않았다.
그래서 방법을 바꾸었다.

string 라이브러리의 to_string 함수를 통해 두 숫자 a,b를 문자열로 바꾸고
a+b의 문자열과 b+a의 문자열을 비교하여 정렬하였다.
그 결과 테스트 케이스 1개만 빼고 모두 통과하였다.
남은 테스트 케이스를 고민해보니 [0,0,0]일 경우 출력 값이 "000"으로 나왔기 때문에
이 부분에 대한 예외처리만 하면 통과를 할 수 있다고 생각했다.

---

🚈 풀이 (초기 코드)

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool cmp(int a,int b){
    int cnt_a=0;
    int cnt_b=0;
    int temp_a=a;
    int temp_b=b;
    while(temp_a>=10){
        temp_a/=10;
        cnt_a++;
    }
    while(temp_b>=10){
        temp_b/=10;
        cnt_b++;
    }
    if(cnt_a==cnt_b){
        return a>b;   
    }
    else{
        int mod_a=1;
        int mod_b=1;
        while(cnt_a>0){
            mod_a*=10;
            cnt_a--;
        }
        while(cnt_b>0){
            mod_b*=10;
            cnt_b--;
        }
        if(mod_a>1){
            a%=mod_a;
        }
        if(mod_b>1){
            b%=mod_b;
        }
        return a>b;
    }
}

string solution(vector<int> numbers) {
    string answer = "";
    sort(numbers.begin(),numbers.end(),cmp);
    for(auto p:numbers){
        answer+=to_string(p);
    }
    return answer;
}

🚈 풀이 (제출 코드)

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool cmp(int a,int b){
    string ab = to_string(a)+to_string(b);
    string ba = to_string(b)+to_string(a);
    return ab>ba;
}

string solution(vector<int> numbers) {
    bool check_all_zero=true;
    for(auto p:numbers){
        if(p!=0){
            check_all_zero=false;
            break;
        }
    }
    if(check_all_zero){
        return "0";
    }
    string answer = "";
    sort(numbers.begin(),numbers.end(),cmp);
    for(auto p:numbers){
        answer+=to_string(p);
    }
    return answer;
}