[프로그래머스] 정렬 - 가장 큰 수 / multimap, sort, compare

문제

 

풀이

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

string solution(vector<int> numbers) {
    string answer = "";
    multimap<string, int> map;
    for(auto number : numbers){
        string n = to_string(number);
        while(n.size() < 4) { // numbers의 원소는 0 이상 1,000 이하
            n = n + n;
        }
        n = n.substr(0, 4);
        map.insert(make_pair(n,to_string(number).size()));
    }
    
    for(auto m : map){
        string str = m.first;
        answer = str.substr(0, m.second) + answer;
    }
    
    // "0000" 처럼 맨 앞이 0으로 시작할 경우. 
    if(answer[0] == '0'){
        return "0";
    }
    return answer;
}

 

multimap을 사용한 이유 

• 데이터 값이 들어갈 때 key값을 기준으로 오름차순 정렬이 된다.
• key값이 중복이 가능하다. ( map이 아니라 multimap을 사용한 이유)

 

number의 최댓값이 1000 (legnth = 4)이기 때문에 모두 네 자리 숫자로 만들어 주고, multimap에 넣어 정렬해주었다.

네 자리 숫자로 만든 이유는 1과 10의 경우 4자리로 만들면 1111 > 1010으로 정렬되기 때문이다!

 

 

 

---

다른 사람 풀이

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

using namespace std;

bool compare(const string &a, const string &b)
{
    if (b + a < a + b)
        return true;
    return false;
}

string solution(vector<int> numbers) {
    string answer = "";

    vector<string> strings;

    for (int i : numbers)
        strings.push_back(to_string(i));

    sort(strings.begin(), strings.end(), compare);

    for (auto iter = strings.begin(); iter < strings.end(); ++iter)
        answer += *iter;

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

    return answer;
}

compare로 b+a < a+b 를 비교해 정렬해주었다!

 

sort 를 사용할 때 compare를 어떻게 구현하느냐에 따라 다양하게 정렬할 수 있겠구나를 알게 되었다.

다양한 compare를 구현해봐야지!