programmers 가장 큰 수

programmers : https://programmers.co.kr/learn/challenges?selected_part_id=12198

 

programmers 정렬 level2 가장 큰 수 문제입니다.

 

문제를 푸는 방법은 2가지가 있습니다. (+힌트 는 맨마지막에.. )

 

핵심은 수를 대체 어떤식으로 비교하냐 인데

예제의 6 2 10은 이해하셨겠지만 6210이 최대의 수가 됩니다.

예제에서 큰 힌트를 주었습니다. 3 과 30 입니다.

3, 30 => 330, 303 둘 중에서는 330이 더 크게되니 3이 30보다 크게끔 만들어야 한다는 뜻입니다.

 

애초에 범위는 10만이기 때문에 n^2로 해결할 수 없습니다. 즉 브루트포스가 불가능하단 소립니다.

 

방법1 : 수를 직접 범위내의 자릿수까지 만들어주는 방법

문제에서 수는 4자리 이하로만 주어진다고 했습니다. 이건 정말 큰 힌트가 됩니다.

모든 수를 4자리 이하로 만들어버리면 대수비교가 가능해집니다.

예제를 보면 6000, 2000, 1000 이렇게 만들 수 있는 것입니다.

결국 그대로 정렬되게 되고, 6,2,10만 따오면 되는 것입니다.

 

그럼 3과 30은 어떻게 비교할까요?

3000, 3000이 되기때문에 무작정 *10 을 해서는 안된다는 뜻이 됩니다.

그렇다고 무작정 뒤에 임의의 숫자를 집어넣는다 생각할 수 있는데 

3999, 3099 는 좋은 비교대상이 되겠지만, 3, 34도 임의의 숫자 9? 로도 가능할까요?

3999, 3499 를 비교하면 3>34 가 되지만, 334 와 343 은 343이 더 크게됩니다.

즉, 자기자신을 뒤에 계속 이어붙여줌으로써 문제를 해결할 수 있습니다.

3333, 3434 이런식이 되게 됩니다.

 

방법2 : 스트링을 합친 비교

정말 간단한 방법입니다.

3과 34를 예를 들면

 

sort의 compare 함수를 구현할 때 3+34 와 34+3 을 비교하는 것입니다.

문자열은 결국 334, 343이 되고 343이 더 큰값이 되어 34>3 이 되게끔 바로 정렬이 가능합니다.

 

아래는 방법2로 구현한 코드입니다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
 
bool cmp(string& a, string& b) {
    return (a + b) > (b + a);
}
 
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);
 
    bool check = false;
    for (int i = 0; i < v.size(); i++) {
        answer += v[i];
        if(v[i] != "0") check = true;
    }
    
    if(!check) answer = '0';
 
    return answer;
}