[프로그래머스] Level.2 정렬-가장 큰 수

코딩테스트 연습 - 가장 큰 수

 

문제설명

입출력예

 

가장 큰 숫자가 나오게 끔 숫자를 정렬하는 과정이 필요하다.

한자리 수와 두자리 수 이상의 숫자가 함께 주어지기 때문에  이어 붙였을때 큰 숫자가 나오게 정렬하기 위해서는 우리가 그에 맞는 비교함수를  구현해줘야 한다.

 

일단 이 코드를 구현하기 위한 아이디어는 다음과 같다

여기서 말하는 가장 큰 숫자란 숫자들을 이어붙였을때 가장 큰 수가 나오는 경우다

우리는 그러면 숫자 두개를 이어 붙인다고 가정하고 비교를 하면된다

주어진 numbers 배열의 6과 10을 비교할때  (string가정) 6+10=610, 10+6=106이다.

610>106이므로 더 앞쪽에 정렬되어야 한다.

문제를 풀기위한 코드는 다음과 같다

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

string solution(vector<int> numbers) {
	string answer = "";
	vector<string> s;
	for (int i = 0;i < numbers.size();i++) {
		s.push_back(to_string(numbers[i]));
	}
	sort(s.begin(), s.end(), compare);
	for (int i = 0;i < numbers.size();i++) {
		answer += s[i];
	}
    if(answer[0]=='0') answer='0';
	return answer;
}

 

젤 처음에 비교함수를 구현할때 compare함수에서 오류가 났다.

알아보니 sort를 위한 compare 함수는 반드시 strict weak ordering을 만족해야 한다고 한다.

즉, a==b인 경우에는 a<b도 false이고 a>b도 false가 되어야 한다.

근데 그런 오류를 고민하지 않아도 이 문제는 쉽게 풀리는 문제였는데 내가 괜히 어렵게 생각했다.

아직도 compare에 익숙하지 않은것 같아서 좀 더 공부가 필요한것 같다.