백준16496번 - XML 자바스크립트(Node.js)풀이

난이도: 플래티넘 5

문제

음이 아닌 정수가 N개 들어있는 리스트가 주어졌을 때, 리스트에 포함된 수를 나열하여 만들 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나머지 수는 0으로 시작하지 않으며, 0이 주어지는 경우 0 하나가 주어진다.

 

출력

리스트에 포함된 수를 나열하여 만들 수 있는 가장 큰 수를 출력한다. 수는 0으로 시작하면 안되며, 0이 정답인 경우 0 하나를 출력해야 한다.

 

출처

University > 한양대 ERICA > 2018 ERICA Software-Up Programming Contest League A F번

 

알고리즘 분류

- 문자열

- 그리디 알고리즘

- 정렬

 

 

---

주어진 숫자들을 조합하여 가장 큰 수를 만드는 그리디 계열 문자열 알고리즘 문제. 자바스크립트의 기본 소트 함수를 응용하면 쉽게 해결할 수 있다.

 

 어떻게 하면 주어진 수들을 조합하여 가장 큰 수를 만들 수 있을까? 기본적으로 주어진 수들을 어떠한 기준을 통해 정렬한 후, 정렬방식(오름차순, 내림차순)에 따라 어레이에서 가장 큰 값을 하나씩 꺼내서 문자열에 붙여준다면 정답이 나오게 될것이다. 이 알고리즘에서 가장 중요한 포인트는 어떠한 방법으로 정렬한 수를 순서대로 조합했을 때 정말로 가장 큰 숫자가 나오는지를 증명하는 것이다. (가장 간단하고 정확한 증명방법은 일단 코드를 제출하는것 !!)

 

1. 주어진 숫자를 정렬하고 합치는 방법

비교함수를 더 큰 숫자를 기준으로 정렬하고 합치게하면 큰 수를 만들 수 없다. 예를 들어 10,476은 987보다 큰 숫자이지만 10,476,987은 98,710,476보다 작다.

 

2. 주어진 숫자를 사전식으로 정렬하고 합치는 방법

사전식으로 정렬하고 합치면 큰 수를 만들 수 없다. 예를 들어 373은 37보다 사전순으로 큰 숫자이지만, 37,337은 37,373보다 작다. 이 방식은 정답에 매우 가깝지만 이 방법은 정답이 아니다.

 

3. 주어진 숫자를 앞뒤로 합쳐봐서 사전식으로 더 큰 숫자가 나오게 정렬하고 합치는 방법

 정답은 2번을 조금 비틀어서 두 숫자를 앞뒤로 붙여봤을때 더 큰 숫자가 나오게 하는 수를 기준으로 정렬해주면 된다. 2번의 방법하고 유사하지만, 두 숫자 자체의 사전적 순서를 비교하는 것이 아닌, 두 숫자의 문자열을 합해봤을때 앞에 붙이면 더해진 전체 문자열이 사전적으로 더 앞에 오게 하는 수를 더 큰 수라고 생각하고 정렬해주는 방식이다. 예를 들어 37과 373을 비교할 때, '37' + '373' 과 '373' + '37'중 사전편집순으로 더 큰 수는 '37373'이다. 따라서 이 수를 구성하는 숫자 중 앞에 오는수인 '37'이 더 큰 숫자인 것이다. 이를 함수로 표현하면 다음과 같다.

 

(a, b) => a+b > b+a ? 1 : -1

 

 마지막으로 모든 숫자가 0으로 구성된 경우 결과가 0의 반복으로 나오는 것을 방지하기 위해 합쳐진 문자열을 BigInt형으로 구성하였다. 테스트케이스의 숫자가 커서 Int형 변환시 올바른 답이 나오지 않는다. 출력 결과에서 BigInt형을 나타내는 수식어인 'n'이 나타나는걸 방지하려고 ' +"" ' 을 통해 다시 문자열로 변환하였다.

 

 

const fs = require('fs');
const stdin = (process.platform === 'linux'
        ? fs.readFileSync('/dev/stdin').toString()
        : `2
0 0`
).split('\n');

const n = +stdin[0];
let arr = stdin[1].split(' ');

(function (){
    arr.sort( (a, b) => a+b > b+a ? 1 : -1);

    let rst = "";
    for(let i=0; i<n; i++){
        rst += arr.pop()
    }
    console.log(BigInt(rst)+"");
})()