[프로그래머스 C++] - 가장 큰 수

문제 : 가장 큰 수

문제 설명

 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 분석

 기본적인 대수 비교로는 풀 수 없는 문제이다. sort()함수에서 compare 부분을 사용자 정의해서 풀면 된다. 그런데 규칙이 만만치 않아 보인다. 어떻게 해야 규칙에 맞게 내림차순으로 정렬할 수 있을까? 정답은 정수로 비교하는 것이 아닌 string 형으로 바꿔 비교하는 것이다. 예를 들어 "34", "30"이 있다면, "3430"과 "3034" 중 어느 것이 큰가를 비교하는 것이다.  

 

 구현

bool compare(const string& a, const string& b)
{
	return (a + b) > (b + a);
}

string solution(vector<int> numbers)
{
	string answer = "";
	vector<string> str_numbers;
	for (size_t i = 0; i < numbers.size(); i++)
	{
		str_numbers.push_back(to_string(numbers[i]));
	}

	sort(str_numbers.begin(), str_numbers.end(), compare);
    	// 예외
	if (str_numbers.front() == "0") return "0";

	for (size_t i = 0; i < str_numbers.size(); i++)
	{
		answer.append(str_numbers[i]);
	}
	return answer;
}


int main()
{
	vector<int> nums = { 3,30,34,5,9 };
	string ans = solution(nums);
	cout << ans;
	return 0;
}

 

 이런 유형을 처음 푼다면 string형으로 바꾼다는 생각을 못하는게 당연한다. 이런 유형은 나올 때마다 눈에 익혀두자!