[Programmers] 가장 큰 수

정답률도 높고 도전한 사람도 꽤 많아서 도전해봤는데, 보니까 이전에도 몇 번 푸려다가 못 풀었었다.

처음에 떠올린 방법은 숫자마다 가중치를 계산하고, 그 값으로 정렬하는 것이었다.
결국 앞에 있는 수가 클수록 이득이기 때문에, 맨 앞자리부터 가중치 1000, 100, 10 ,1 를 곱해준다.
여기서 뒷자리가 맨 앞자리보다 작으면 오히려 차이 * 가중치만큼 값을 빼주는 식이었는데,
이게 하면 할수록 예외가 계속 발견되고 결국엔 818 81/ 676 67 같이 중간까지 같고 뒤에 뭐가 더 붙는 경우에 대해서 확실히 처리하지 못했다.

몇 번 인지했지만 그럼에도 안 고쳐지는게, 나는 한 풀이에 꽂히면 다른 풀이를 생각하지를 못한다. 그래서 계속 삽질을 하게 되는 것 같다. 뭔가 꼴에 자존심이랍시고 다른 사람 풀이도 안 보고 풀겠다고 오기를 쓰는데, 이거 아마 질문하기 참고 안 했으면 이틀은 더 이 풀이로 고민했을 것 같다.

삽질 하루종일 한 코드

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

string solution(vector<int> numbers) {
    string answer = "";
    vector<pair<int,string>> v;
    
    for(int i=0; i<numbers.size();i++){
        int n = numbers[i];
        string s =to_string(numbers[i]);
        int val=(s[0]-'0')*10000;
        int tmp=1000;
        
        for(int j=1;j<s.size();j++)
{                        
            if(s[0]==s[j]){
                if(s[j]>s[j-1]) val+=s.size();
                if(s[j]<=s[j-1]) val-=s.size();
            }
            if(s[0]<s[j]){
                val+=(s[j]-'0')*tmp;
            }
            else val-=((s[0]-s[j]))*tmp;
            tmp/=10;
        }
      
        //cout<<val<<endl;
        v.push_back(make_pair(val, s));
    }
    
    sort(v.begin(), v.end());
    
    for(int i=v.size()-1;i>=0;i--){
        answer+=v[i].second;
    }

    return answer;
}

사실 실제 풀이는 생각보다 간단했다.
string 으로 두 값을 순서를 바꿔가면서 조합하고, 더 큰 경우로 배치해주면 되는 것이었다.
생각보다 단순하게 생각해야지 풀리는 문제들도 있는 것 같다.

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

bool compare(int n1, int n2){
    string s1 = to_string(n1);
    string s2 = to_string(n2);
    int n3 = stoi(s1+s2);
    int n4 = stoi(s2+s1);
    
    return n3>n4;
    
}

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