프로그래머스 문제풀이-가장 큰 수 (with C++)

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

---

문제 설명

• 숫자 배열이 주어지고 각 숫자들을 재 배치 해서 가장 큰 수를 return 하는 문제

• 간단한 정렬 문제이다.

---

초기 풀이법

• C++ 의 algorithm 라이브러리 안에 next_permutation 을 사용하여 순열을 구하고 그 중에 가장 큰 수를 찾는 방식을 택했다.

• 시간 초과는 나지 않았으나 core_dumped 오류가 발생 되었다.

• 파이썬의 itertools와 같이 왠만하면 사용안하고 구현을 먼저해보는게..

---

개정 풀이법

#include <string>
#include <vector>
using namespace std;
bool sort_def(string a,string b){
    return a+b>b+a;
}

string solution(vector<int> numbers) {
    string answer = "";
    int max = 0;
    vector<string> sv;
    for(auto idx:numbers){
        sv.push_back(to_string(idx));
    }
    
    sort(sv.begin(),sv.end(),sort_def);
    
    if(sv.at(0)=="0")return "0";
    for(auto c:sv){
        answer+=c;
    }
    
    return answer;
}

• 오히려 파이썬 보다는 간단한 구현 방식인거 같다. 아직 함수 사용법에 서툴러서 찾아가면서 하긴했지만 ..

1. 우선 int형식의 vector를 to_string을 이용하여 string형식 vector에 재 정의 한다.
2. 재 정의된 vector를 sorf_def라는 사용자 정의 함수로 정렬을 시켜준다.
   • sort_def의 역할
     - ex) "3"과 "30"이 있을 때 숫자로 비교하면 30이 더 큰 수 이지만 우리는 조합하여 큰수를 만들어야 되기 때문에 "330" > "303" 이므로 두 string을 더한 후 큰 값 기준으로 정렬을 시켜준다.
     
3. 정렬된 vector에서 가장 앞의 문자가 0이면 이후에 문자도 다 0이므로 "000000" -> "0" 으로 나타내기 위해 가장 앞의 문자가 0이면 그냥 0을 return 한다.
   아닌 경우에는, answer문자열에 더해서 결과 값을 출력 한다.