프로그래머스 lv2 - 가장 큰 수

https://school.programmers.co.kr/learn/courses/30/lessons/42746

프로그래머스

 

실패한 1차 시도

처음에는 완전 탐색 방식으로 코드를 풀고자 시도하였다.

1. 문자열로 가능한 조합을 모두 찾고
2. 해당 조합 중 가장 큰 조합을 찾는 것이다.

조합을 찾기 위한 방법으로 next_permutation 함수를 사용하였다.

문제점

해당 풀이의 문제는 시간 복잡도가 매우 높다는 것이다.

next_permutation은 정렬된 데이터에 대해서 순열을 구할 수 있다.

우선 정렬이 먼저 필요하다.
그리고 다음 경우의 수가 없을 때까지 순열을 바꿔줘야 하고
반복문 내부에서 순열의 원소들을 문자열로 붙여야한다

• 정렬 : O(N log N)
• 순열의 경우의 수에 따른 do-while 반복문 : O(N!)
• 반복문 내부 :  O(N)

예상되는 전체 시간 복잡도는 O(N! × N)이다.

배열의 길이가 최대 100000까지 가능한데 N!의 시간 복잡도는 매우 치명적이다.
그래서 다른 방법으로 접근해야 했다.

---

2차 문제 풀이

시간 복잡도 때문에 조합은 쓸 수 없다.
그렇다면 어떻게 여러 경우의 수를 고려하며 가장 큰 조합을 만들 수 있을까?

힌트는 해당 문제의 카테고리에 있었다.

정렬 카테고리에 속하는 문제였던 것이다.
그럼 이 문제는 정렬로 풀어야 한다.

또한, 모든 조합의 경우의 수를 알 필요는 없고 가장 큰 경우만 알면 된다.
"두 수를 어떻게 붙였을 때 큰 수가 되는가?"에 집중하였다.

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

이를 위해 정렬을 위한 비교 함수를 위와 같이 구성하였다.

다음과 같은 예시를 기준으로 테스트를 해보면

3+30 = 330, 30+3 = 303 ➡️ [3, 30, 34, 5, 9]
30+34 = 3034, 34+30= 3430 ➡️[3, 34, 30, 5, 9]
...

이런 정렬 과정을 거치면서 더 큰 수를 만들 수 있는 순서로 정렬되게 된다.
이를 바탕으로 아래와 같이 코드를 작성하며 문제를 풀이하였다.

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

string solution(vector<int> numbers) {
    string answer = "";
    
    vector<string> strNums;
    for (int num : numbers) {
        strNums.push_back(to_string(num));
    }
    
    sort(strNums.begin(), strNums.end(), compare);
   
    if (strNums[0] == "0") return "0";

    for (string s : strNums) {
        answer += s;
    }
    
    return answer;
}