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

문제

이렇게 numbers배열이 주어지면 각 원소들을 조합해서 가장 큰 수를 만드는 문제이다.

---

접근

처음 시도했던 접근 방법은 이렇다.
일단, 두 수를 비교했을 때 어떤 수가 앞에 와야 하는지 생각해봤다.

1. 맨 앞자리수가 커야 한다.
예를 들어서, 18과 2를 비교했을 때 만들 수 있는 조합은 182와 218인데
218이 더 큰 것을 보면 앞 자릿수가 커야 조합했을 때 큰 수 를 만들 수 있다.

2. 앞자리수가 같다면 마찬가지 논리로 뒷자리 수가 커야 한다.
예를 들어서, 28과 27을 비교했을 때 만들 수 있는 조합은 2827과 2728인데
2827이 더 큰 것을 보면 알 수 있다.

3. 모든 자리의 숫자가 같지만 자릿수가 다르다면, 자릿수가 같을 때까지 맨 앞의 수를 넣은 후 비교한다.
예를 들어서 382와 38을 비교했을 때,
382와 (38에 맨 앞 자릿수인 3을 붙인 383을 비교한다.
그렇게 하면 38382가 만들어지는데 이것은 다른 조합인 38238보다 더 큰 것을 알 수 있다.

4. 이렇게 해서도 모두 같으면 더 작은 수가 더 큰 조합을 만들 수 있다.
예를 들어서, 383과 38을 비교했을 때 만들 수 있는 조합은 38383과 38338인데
38383이 더 큰 것을 보면 수가 더 적은 38이 앞에 있는 상황인 것을 알 수 있다.

이렇게 해서 코드를 짜면 아래와 같다.

bool compare(const int& a, const int& b){
    string sa=to_string(a), sb=to_string(b);
    string tmp1=sa+sb, tmp2=sb+sa;
    return stoi(tmp1)>stoi(tmp2);
}

---

시행착오

하지만 이 코드에는 예외상황이 발생한다.

예를 들어서 [10,101,1]이 주어졌을 때 위의 논리대로 하면

1. 번으로는 모두 같고, 2. 번으로도 모두 같다.

이제 3. 번으로 비교하면 1 > (10 , 101) 순서가 된다.

이것을 4. 번으로 비교하면 1 > 10 > 101 이고, 이것으로 만든 수는 110101이 된다.

하지만, 실제로 가장 큰 수는 110110, 즉 1 > 101 > 10 순서가 된다.

---

깨달음

문제를 너무 복잡하게 생각했다.

이 문제는 여러 가지 수의 조합을 따져봤을 때, 가장 큰 조합을 만드는 것이다.

그렇다면 두 가지 수를 비교했을 때도 조합을 따져본 뒤, 가장 큰 조합을 만들 수 있는 배열을 만들어 주면 되는 것이다.

다시 위의 예를 들어서 101과 10을 비교한다고 했을 때

두 수로 만들 수 있는 조합 10110과 10101을 비교했을 때 10110이 더 크므로

101 > 10 순서를 만들어 주면 되는 것이다.

이것을 코드로 구현해보면 아래와 같다.

bool compare(const int& a, const int b){
    string sa=to_string(a), sb=to_string(b);
    if(sa.length()==sb.length()) return a>b;
    while(sa.length()!=sb.length()){
        if(sa.length()>sb.length()) sb.push_back(sb.front());
        if(sa.length()<sb.length()) sa.push_back(sa.front());
    }
    if(stoi(sa)==stoi(sb)) return a<b;
    return stoi(sa)>stoi(sb);
}

이렇게 하면 모든 배열을 가장 큰 수의 조합으로 만들어 줄 수 있다.

단 한 가지 예외 사항이 있는데 [0,0]이 주어졌을 경우에는 00이 출력되지만 답은 0이다.

이것을 예외 처리해주면 정답 코드는 아래와 같다.

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

using namespace std;

bool compare(const int& a, const int& b){ /* 위와 같음 */ }

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

앞으로

문제가 주어졌을 때, 문제를 곧이곧대로 보는 방법도 시도해보는 연습을 해야겠다.