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

[문제]

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

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

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

제한 사항

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

입출력 예

 

[6, 10, 2]	6210
[3, 30, 34, 5, 9]	9534330

 

[풀이]

 

1) 시간 복잡도 고려 해야 한다. (배열의 최대 길이는 100,000 이므로 n^2이면 100억이 넘는다.)

 

2) 처음에는 bubble 소트를 약간 변형해서 두 값을 더한 값이 더 큰 숫자를 앞으로 보냈다. 하지만 버블소트의 시간 복잡도는 n^2이기 때문에 TC 1,2,3,5,6 이 시간초과가 발생했다. 

 

3) 그래서 sort 알고리즘을 사용하면서 세번째 파라미터로 compare 함수를 재정의하여 보내줬다. 

 

4) 정렬은 위에서와 같이 인접한 두 수를 더한 값이 더 큰 값을 앞으로 보내도록 한다. 

여기서 중요한 점은 "더 크거나 같은 " 값을 앞으로 보내야 한다. 

 

5) 정렬된 값을 문자열로 만들어서 리턴한다. 

 

---

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
typedef long long ll;
 
bool compare(const int &a, const int &b) {
    string tmp_a = to_string(a) + to_string(b);
    string tmp_b = to_string(b) + to_string(a);
    
    if (tmp_a <= tmp_b) {
        return false;
    }
    return true;
}
//1,2,3,5,6 시간 초과 
string solution(vector<int> numbers) {
    string answer = "";
    
    int n = numbers.size();
   
    //모두 0인지 확인 
    ll res = 0;
    for (int i = 0; i < n; i++) {
        res += numbers.at(i);
    }
    
    if (res == 0)  answer = to_string(0);
    
    //정렬 -> o(nlogn)으로 해야한다. 
    else {
//         for (int i = 0; i < n; i++) {
//             for (int j = 0; j < n-i-1; j++) {
//                 string s1 = to_string(numbers[j]) + to_string(numbers[j+1]);
//                 string s2 = to_string(numbers[j+1] )+ to_string(numbers[j]);
                
//                 if (s1 < s2) {
//                     int tmp = numbers[j];
//                     numbers[j] = numbers[j+1];
//                     numbers[j+1] = tmp;
//                 }
//             } 
        sort(numbers.begin(), numbers.end(), compare);
          for (int i = 0; i < n; i++) {
          answer += to_string(numbers[i]);
      }
    
       }
    return answer;
}