[알고리즘C++] 가장 큰 수

오늘의 문제

4시간은 붙들고 있었는데 도저히 안 풀린다. 하..

가장 큰 수

나의 풀이?

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;
string solution(vector<int> numbers) {
    string answer = "";
    priority_queue<pair<int, int>> q;
    for(int i;i<numbers.size();i++){
        string f = to_string(numbers[i]);
        for(int j=to_string(numbers[i]).size();j<3;j++){
            f += f[0];
        }
        q.push(make_pair(stoi(f), numbers[i]));
    }

    
    while(!q.empty()){  
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> sec;
        priority_queue<pair<int, int>> sec_rev;
        int f = q.top().first;
        
        bool rev = false;
        if(to_string(q.top().second)[0] > to_string(q.top().second)[1])
            rev = true;
        
        while(q.top().first == f && !q.empty()){
            string s = to_string(q.top().second);
            if(rev)
                sec_rev.push(make_pair(s.size(),q.top().second));
            else
                sec.push(make_pair(s.size(),q.top().second));
            q.pop(); 
        } 
        if(rev){
            while(!sec_rev.empty()){
            if(answer == "0")
                answer = "";
            answer += to_string(sec_rev.top().second);     
            sec_rev.pop();
        }
        }else{
        while(!sec.empty()){
            if(answer == "0")
                answer = "";
            answer += to_string(sec.top().second);     
            sec.pop();
        }
        }     
    }    
    return answer;
}

모범 답안

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(const string &a, const string &b) {
	return a + b > b + a ? true : false;
}
string solution(vector<int> numbers) {
	string answer = "";
	vector<string> strArr;
	for (int i = 0; i < numbers.size(); i++) {
		strArr.push_back(to_string(numbers.at(i)));
	}
	sort(strArr.begin(),strArr.end(),cmp);
	for (string str : strArr) {
		answer += str;
	}
	if (answer[0] == '0')
		return "0";
	return answer;
}

배울 점

• 나는 한참 멀었다
• string 비교만 쓰면 이렇게 간단하게 풀린다.
• 간단한 string sort 함수를 이해하며 공부하자
  
• true이면 그대로, 아니면 뒤집는 방식으로 진행되는 듯
• 위 문제에서 string두개를 합쳤을 때를 비교해서 sorting후 가장 큰 값이 되도록 한다.
• 아직 익숙하지 않아서 string 관련 문제를 더 찾아봐야겠다는 생각이 든다.