프로그래머스 - 가장 큰 수(c++, javascript)

문제 설명

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

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

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

 

제한 사항

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

 

입출력 예

 

풀이

문제가 상당히 짧아서 쉽게 생각했는데 잘못 접근하면 한 없이 어려운 문제인 것 같다..

고민끝에 찾아봐서 풀 수 있었다..... ... ...

sort를 사용하여 원소를 2개씩 비교해 정렬해 나가는데

이 때의 원소를 문자열 a, b라고 했을 때 a+b와 b+a의 값중 더 큰 값을 가지는 경우가 바로 더 앞에 와야할 원소이다.

 

문제에서 2번째 예시를 보면 예를 들어, 3과 30을 비교한다고 했을 때 330 vs 303 둘 중에 330이 더 크다.

따라서 3이 30보다 앞에 나와야 하는 것을 알 수 있다.

이 과정을 반복하여 정렬하면 문제를 해결 할 수 있다.

 

짧지만 어려웠던 문제

 

c++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(int a, int b){
    string ab = to_string(a) + to_string(b);
    string ba = to_string(b) + to_string(a);
    
    return ab > ba;
}

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

 

javascript

function compare(a, b){
    const ab = String(a) + String(b);
    const ba = String(b) + String(a);
    
    return ba - ab;
}

function solution(numbers) {
    var answer = '';
    
    numbers.sort(compare);
    
    if(numbers[0] === 0) return '0';
    
    answer = numbers.reduce((acc, cur)=>{
        return String(acc) + String(cur);
    })
    
    return answer;
}