정렬 [프로그래머스] 가장 큰 수

문제 자체는 전혀 어려울 것 없는 무난한 수준의 문제이다.

중요한건

• 정렬을 어떤 기준으로 하느냐
• 정렬 알고리즘을 틀리지 않고 짜느냐
• 반례를 잘 잡느냐

이 세가지일 것이다.

C++의 정렬

C++에서의 정렬을 클래스나 구조체 선언부에서 operator <를 오버라이딩하는 방법,
정렬 함수를 만들어 algorithm 헤더에서 제공하는 sort의 3번째 인자로 넣어주는 법 2가지가 있다.

반례 잡기 1

처음엔
숫자 7, 76, 77, 78 과 같은 비슷한 우선순위를 가질법한 예시에서 나열을 자체적으로 해보았다.

여기서 내가 처음 생각한 정렬 방법은
7과 76이 있을 때
둘의 길이가 같아질때까지 큰수의 앞자리에서부터 작은수에 붙여주는 방식이었다.

76의 앞자리 7을 7뒤에 붙여서 77, 76을 비교하는 식이다.

하지만 이렇게 하면 문제가
97, 979라는 숫자를 비교할 때는 우선순위가 서로 같아지게 되는데,
둘 중 앞에 있는 수에 따라 97979, 97997이라는 다른 결과물이 나온다는 것이다.

결론적으로 내린 결론은 두 숫자 a,b 가 있으면 a뒤에 b를 , b 뒤에 a를 붙이는 것이 가장 명확히 정렬할 방법이라는 것을 알았다.

반례 잡기 2

중복된 수가 여러개 나올 수 있다. 특히 0만 나오는 경우도 고려해야 한다. 이때는 0이 여러개 붙여도 결국 0이므로, 모든 수가 0인 경우를 고려하는 조건문을 포함시켰다.

정답 코드

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

using namespace std;

bool cmp(int numA, int numB) {
	string a = to_string(numA);
	string b = to_string(numB);
	a.append(b);
	b.append(a);
	return (a > b);
}

string solution(vector<int> numbers) {
	string answer = "";
	bool onlyZero = true;
	sort(numbers.begin(), numbers.end(), cmp);
	for(int i=0; i<numbers.size(); i++){
		if(numbers[i]!=0) onlyZero = false;
		answer.append(to_string(numbers[i]));
	}
	if(onlyZero) return "0";
	return answer;
}