프로그래머스_가장 큰 수

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

코딩테스트 연습 - 가장 큰 수 | 프로그래머스

정렬 문제, LV2

해당 문제를 풀며 알게된 것은 문자열 '+' 연산은 교환법칙이 성립하지 않는다는 것이다.

당연히 a + b 일 경우 a를 기준으로 b를 붙이게 되는 것이다.

해당 특성을 활용해 가장 큰 수를 만들고 싶으면 두 int 정수 간에 a + b 로 만들어진 문자열이 큰 것인지 b + a 로 만들어진 문자열이 큰 것인지만 비교하는 되는 문제였다.

 

처음 풀이가 바로 떠오르지 않아서 위의 로직을 일일이 구현하였다. 그 결과 당연히 시간 초과가 났다.

그리고는 원래의 로직을 통해 comp라는 함수를 통해 해결하였다.

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

bool compare(string as, string bs){
    // 문자열 사이즈 같으면 높은 순
    if(as.size() == bs.size())
        return stoi(as) > stoi(bs);
    
    // 다르면
    else{
        // 다른 것들 찾을 때 까지
        int idx_a =0, idx_b = 0;
        while(true){
            // 다르면
            if(as[idx_a] != bs[idx_b])
                break;
            
            // 같으면 다음 것 비교
            idx_a = (idx_a+1)%as.size();
            idx_b = (idx_b+1)%bs.size();
        }
        // 높은 순
        return as[idx_a] > bs[idx_b];   
    }
}

// 어느쪽으로 붙이는게 큰 것인지
bool comp(string a, string b){
    return (a + b > b + a) ? true : false;
}

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> n(numbers.size());
    for(int i=0;i<n.size();i++)
        n[i]=to_string(numbers[i]);
    
    // 정렬
    sort(n.begin(), n.end(), comp);
    
    // 정답 생성
    if(n[0]=="0") return "0";
    for(auto sc : n){
        answer += sc;
    }
    return answer;
}