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

1. 문제 링크

코딩테스트 연습 - 가장 큰 수

2. 소스코드

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

using namespace std;
bool cmp(string s1,string s2){
    int lastindex=min(s1.length(),s2.length())-1;
    for(int i=0;i<=lastindex;i++){
        if(s1[i]==s2[i]){
            if(i==lastindex){
                if(s1.length()==s2.length()){
                    //아예 같은 문자열
                    return false;
                }
                else{
                    return s1 + s2 > s2 + s1;
                }
            }
            continue;
        }
        else return s1[i]>s2[i];     
    }
}
string solution(vector<int> numbers) {
    string answer = "";
    vector<string> v;
    for(int n:numbers){
        stack<int> s;
        if(n==0){v.push_back("0");continue;}
        while(n>0){
            s.push(n%10);
            n/=10;
        }
        string temp;
        while(!s.empty()){
            temp+=s.top()+'0';
            s.pop();
        }
        v.push_back(temp);
    }
    sort(v.begin(),v.end(),cmp);
    for(string str:v){
        answer+=str;
    }
    if(answer[0]=='0')return "0";
    return answer;
}

+
그냥

bool cmp(string s1,string s2){
    return s1+s2>s2+s1;
}

해도 통과 됨.

3. 노트

3-1.연산자(cmp) 오버로딩

Java에서 comparator를 오버로드하는 것처럼, C++에서 sort 함수에 세 번째 인자로 compare함수를 넣어 (보통 나는 bool cmp로 작성함) 사용자 지정 정렬을 할 수 있다.
이 때 주의할 점은 매개함수의 두 파라미터 중, 첫 번째 파라미터가 더 앞으로 정렬되는 파라미터이기 때문에 두 파라미터 간 관계를 잘 표현해야 한다. 즉,

bool compare(int a, int b){
	return a > b;
}

여기서 첫 번째 파라미터인 a가 더 앞으로 정렬되는 값이고, 여기서 a>b이기 때문에 이 매개함수를 쓰면 숫자가 내림차순으로 정렬된다.
마찬가지로 내가 정의한 cmp 함수에서, 더 앞으로 정렬되는 문자열인 s1은 s1[i]>s2[i]라는 규칙을 지켜야 한다.

3-2.Strict weak ordering

테스트 시행 시와 다르게 실제 채점을 돌려 봤을 때 segmentation fault가 많이 발생했는데, 아마 처음에는 s1==s2일 때 s1>=s2를 반환해서 오류가 났겠지 싶다.
두 파라미터가 같은 값을 가질 때에는 return false를 해야 한다.
이게 무슨 뜻이냐면, s1==s2일 때, s1>s2도 false고 s1<s2도 false여야 한다는 말이다.

3-3.고려할 점

사실 내가 계속 디버깅 한 로직은

bool cmp(string s1,string s2){
    int lastindex=min(s1.length(),s2.length())-1;
    for(int i=0;i<=lastindex;i++){
        if(s1[i]==s2[i]){
            if(i==lastindex){
                if(s1.length()>s2.length()){
                    //s2가 더 짧은 문자열
                    if(s1[i+1]==s2[i])return s2[i]>s2[i-1];
                    return s2[i]<s1[i+1];
                }
                else if(s1.length()==s2.length()){
                    //같은 문자열
                    return false;
                }
                else{
                    //s1이 더 짧은 문자열
                    if(s2[i+1]==s1[i])return s1[i]>s1[i-1];
                    return s1[i]>s2[i+1];
                }
            }
            continue;
        }
        else return s1[i]>s2[i];     
    }
}

이었는데, "566">"56", "544"<"54" 를 제대로 정렬하지 못했다. 대체 어디서 오류가 났는지는 차차 알아봐야지.. 🥲