1. 문제

난이도: Level 2
카테고리: 정렬

2. 풀이 방법

일반적으로 수를 비교해가며 정렬하는 방법은 고려할 것이 너무 많아 비효율적이며, 시간 초과가 발생한다.
따라서 새로운 풀이 방식을 고안해내야 한다.

우리가 할 것은 결국 합쳐서 더 큰 수를 만들어 내는 것이다.
따라서 수를 합쳤을 때 더 큰 것을 sort 의 정렬 기준으로 정한다.

2-1. sort 사용자 정의 비교 함수

C++에서 제공하는 sort() 의 경우, 사용자 정의 비교 함수를 사용할 수 있다.

bool comp(string s1, string s2){
    int temp1 = stoi(s1 + s2);
    int temp2 = stoi(s2 + s1);
    
    return temp1 > temp2;
}

(s1 + s2)와 (s2 + s1)을 비교하여, 더 큰 값을 만드는 순서가 앞에 오도록 한다.
temp1 > temp2가 true이면 s1이 s2보다 앞에 오도록 정렬된다.

sort() - 사용자 정의 정렬
sort 함수는 두 요소를 비교할 때 두 요소의 상대적인 순서를 결정하는 기준으로 bool 값을 반환하는 비교 함수를 사용한다.

• sort(nums.begin(), nums.end(), comp);
  • comp(a, b)가 true이면 a가 b보다 앞에 오도록 정렬된다,
  • comp(a, b)가 false이면 b가 a보다 앞에 오도록 정렬된다.

2-2. 맨 앞이 0인 경우

입력이 {0, 0, 0} 일 경우에는 정답이 '000'이 될 수 있다.
따라서 해당 경우를 따로 처리해주어야 한다.

if(answer[0] == '0')
    answer = "0";

3. 구현

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

using namespace std;

bool comp(string s1, string s2){
    int temp1 = stoi(s1+s2);
    int temp2 = stoi(s2+s1);
    
    return temp1 > temp2;
}

string solution(vector<int> numbers) {
    string answer = "";
    
    vector<string> nums;
    for(int num: numbers)
        nums.push_back(to_string(num));
    
    sort(nums.begin(), nums.end(), comp);
    for(string num: nums)
        answer += num;
    
    if(answer[0] == '0')
        answer = "0";
    
    return answer;
}

• 느낀점...
  • string을 그대로 이용하지 않고 포인터로 풀이하는 방법도 있다.
    이 방법이 풀이의 정석인듯..