[프로그래머스 코딩테스트 고득점 Kit - 정렬] 가장 큰 수

정렬 문제

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

 

---

[문제 풀이]

 

주어진 정수를 잘 조합하여 가장 큰 수를 만드는 문제입니다.

 

단순하게 생각하자면 모든 조합을 전부 구하고 가장 큰 수를 확인할 수도 있습니다.

numbers의 길이가 n, numbers원소의 길이가 l이라 하면 시간 복잡도는 $O(n! \, n^2 \, l)$의 시간 복잡도를 갖습니다.

(모든 조합을 구하는 시간 복잡도 $O(n!)$, 길이가 $nl$인 문자열들 중 최댓값을 찾는 시간 복잡도 $O(n \, nl)$

n의 최대가 10만이므로 말도 안 되는 풀이입니다.

 

모든 원소에 대한 조합을 전부 구하고 비교하는 과정이 매우 비효율적입니다.

 

하지만 2개의 원소만 뽑아서 구해본다면,

예를 들어 numbers가 [21, 394]라고 가정하면 21394와 39421만 비교하면 됩니다.

 

2개의 원소만 뽑아서 보는게 무슨 소용이 있을까요?

정렬을 떠올린다면 소용이 있습니다.

 

정렬은 두 개의 원소를 비교한 후 서로의 위치를 바꾸는 과정을 반복하여 원소들을 특정 기준에 맞춰 나열합니다.

즉 정렬 기준을 두 원소 A, B를 받아 A + B와 B + A를 비교하는 방식으로 바꾼다면 numbers 배열을 나열했을 때 가장 큰 수 혹은 가장 작은 수를 만들 수 있게 됩니다.

 

정렬의 시간 복잡도는 $O(nlogn)$이고 매 정렬마다 A + B, B + A를 비교하는 시간 복잡도는 $O(1)$이므로 위 풀이의 총 시간 복잡도는 $O(nlogn)$입니다.

n이 10만이므로 충분히 시간 제한을 통과할 수 있습니다.

 

하지만 위의 과정으로 풀어도 틀리는 케이스가 존재합니다.

numbers가 [0, 0]이라면 답은 "0"이지만 numbers를 나열하면 "00"입니다.

 

즉, numbers를 나열했을 때, "00 ... 0"의 꼴이라면 "0"을 출력시키면 됩니다.

 

더 간단한 방법으로는 정렬을 마친 numbers[0]가 0이라면 "0"을 출력시키면 됩니다.

A + B와 B + A를 비교하는 방법으로 가장 큰 수를 만들면 0은 가장 우선 순위가 낮게 정렬됩니다.

그럼에도 불구하고 가장 앞자리인 numbers[0]이 0이라면 적어도 "0 ..."의 형태를 띠고 있음을 나타냅니다.

그러므로 "0"으로 출력해도 문제가 없습니다.

 

---

[소스 코드]

 

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

using namespace std;

bool cmp(int a, int b) {
    string s1, s2;
    stringstream ss;
    
    ss << a << b;
    s1 = ss.str();
    
    ss.str("");
    
    ss << b << a;
    s2 = ss.str();
    
    return s1 > s2;
}

string solution(vector<int> numbers) {
    sort(numbers.begin(), numbers.end(), cmp);
    
    stringstream ss;
    for (int n : numbers) {
        ss << n;
    }
    
    if (numbers[0] == 0) return 0;
    else return ss.str();
}