프로그래머스 - 가장 큰 수(C++)

문제 출처:

문제 난이도

Lv 2

문제 접근법

문자열 정렬 문제

통과 코드

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

using namespace std;

bool comp(string a, string b){
    return a + b > b + a;
}

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

피드백

당연히 정렬과 조합을 이용한 문제라고 생각했다.

string solution(vector<int> numbers) {
	string answer = "";
	sort(numbers.begin(), numbers.end());
	vector<string> num;
	do {
		string res = "";
		for (int i = 0; i < numbers.size(); i++) {
			res += to_string(numbers[i]);
		}
		num.push_back(res);
	} while (next_permutation(numbers.begin(), numbers.end()));

	sort(num.begin(), num.end(), greater<string>());
	answer = num[0];
	return answer;
}

이렇게 풀었는데 모든 테스트케이스가 시간초과 (11번 제외)가 났다. 대체 이걸 조합을 이용해서 푸는게 아니면 어떻게 푸는 거란 말이냐?!? 하고 다른 풀이를 참고했다.
그래도 테케 11번에서 에러가 나길래 봤더니 만약 값이 0 0 0 이런식으로 들어오면 answer은 "0"이 아닌 "000" 으로 나와 실패하게 된다. -그래서 앞서 시간초과 코드에도 다 시간초과 일 때, 11번만 시간초과 없이 실패라고 뜻 것-

조건을 걸어서 모든 테케가 통과하게 끔 했다. 프로그래머스는 레벨2라도 방심할 수 가 없다는 걸 다시 깨닫게 해준 문제..