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

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

풀이

만약 늘 풀던 방법대로 풀었다면 백트레킹을 사용해서 문제를 풀었을 것 같다. 하지만 생각해보니 정렬이라는 좋은 방법이 있었다...!!

Q) 어떻게 정렬하지?

numbers 벡터에서 숫자 두개를 서로 앞,뒤로 번갈아 이어붙여서 크기를 비교했을 때 더 큰 수가 나오도록 하는 값이 앞으로 가도록 정렬했다.(function cmp)

Q) cmp 함수에서 string으로 비교 이유는?

숫자들로만 된 문자열이고 둘 다 자릿수가 같다면 굳이 int형으로 바꾸지 않더라도 비교 가능하다.

Q) solution 함수에서 마지막 return 작성

만약 numbers 벡터 안에 0, 0, 0 이렇게 들어있다면 answer는 "000"문자열을 return 하게 된다. 그래서 만약에 answer의 첫글자가 0이라면 모든 수가 0일 경우에만 발생하는 경우이므로 "0"을 return하도록 해준다.

시간 복잡도

numbers의 벡터에 원소 개수가 n개라면 정렬의 시간 복잡도는 nlogn이다.
-> O(nlogn)

코드

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

using namespace std;

bool cmp(int num1, int num2){
    string s1 = to_string(num1) + to_string(num2);
    string s2 = to_string(num2) + to_string(num1);
    return s1 > s2;
}
string solution(vector<int> numbers) {
    string answer = "";
    sort(numbers.begin(), numbers.end(), cmp);
    for(auto i : numbers) answer += to_string(i);
    
    return answer[0] == '0' ? "0" : answer;
}