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

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

프로그래머스

 

문제 : 

 

 

 

예시 : 

 

 

해결 : 

numbers 배열 안의 숫자들을 적절히 나열하여 가장 큰 수를 구하는 문제이다.

배열의 값의 가장 큰 자리 수의 숫자가 큰 순서대로 나열하면 해결되지 않을까싶었다. 

각 자릿 수가 일치하는 경우, 다음 자릿 수로 넘어가 비교하였다. 비교하는 두 숫자의 길이가 다른 경우에는 길이가 짧은 숫자를 1의 자리까지 비교한 이후에 가장 큰 자릿 수로 돌아가 길이가 긴 숫자의 1의 자리까지 비교하도록 했다. 중간에 더 큰 수가 발견되면 그대로 결과를 반환한다. 

 

[5352, 535, 53]로 예를 들면, 정답은 "535355352"가 되어야한다. 5352와 53을 비교했을 때, 0번 인덱스는 (5, 5)로 일치하고, 1번 인덱스는 (3, 3)으로 일치한다. 53은 다시 가장 큰 자리수로 돌아와 비교를 반복한다. (5, 5)를 다시 비교하고, 마지막으로 (2, 3)을 비교한다. 2가 더 작은 수이기 때문에 [53, 5352] 순으로 정렬된다. 

 

 

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

using namespace std;

bool cmp(int a, int b)
{
    string aa = to_string(a);
    string bb = to_string(b);
    int aidx = 0;
    int bidx = 0;
    int l = aa.size() > bb.size() ? aa.size() : bb.size();
    int cnt = 0; 
    while(true)
    {
        if(aa[aidx] > bb[bidx]) return true;
        else if(aa[aidx] < bb[bidx]) return false;
        if(cnt == l) return false;
        if(aidx < aa.size()) aidx++;
        if(aidx == aa.size()) aidx = 0;
        if(bidx < bb.size()) bidx++;
        if(bidx == bb.size()) bidx = 0;
        cnt++;
    }
    
    return false;
}

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

 

 

문제 테스트 케이스를 꼼꼼히 생각하지 못해 '맞왜틀'을 하다가 다른 사람의 반례를 참고하여 해결했다. 그러던 중 더 좋은 비교함수 작성법을 발견했다. 

 

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;
}

 

 

이 함수를 사용하면 문제가 너무나도 간단해진다...

 

 

 

반례 :

[5352, 535, 53] "535355352"

[0, 0, 0] "0"