20366 같이 눈사람 만들래? (자바스크립트)

문제

언니! 똑...똑똑...똑똑! 같이 눈사람 만들래~? ♪

언니 엘자와 동생 안나에게는 N개의 눈덩이가 있다. 각 눈덩이 i (1 ≤ i ≤ N)의 지름은 Hi 이다. 하나의 눈사람은 두 개의 눈덩이로 구성되며, 눈덩이 하나를 아래에 두고 그 눈덩이보다 크지 않은 다른 눈덩이를 쌓아올리는 방식으로 만들 수 있다. 이때, 눈사람의 키는 두 눈덩이 지름의 합과 같다.

엘자와 안나는 눈덩이 N개 중 서로 다른 4개를 골라서 눈사람을 각각 1개씩, 총 2개를 만들려고 한다. 두 자매는 두 눈사람의 키의 차이가 작을수록 두 눈사람의 사이가 좋을 것이라고 믿는다. 우리는 엘자와 안나가 가장 사이좋은 두 눈사람을 만들기 위해서 도와주려고 한다.

주어진 N개의 눈덩이를 이용하여 만들 수 있는 두 눈사람의 키 차이 중 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (4 ≤ N ≤ 600)이 주어진다.

둘째 줄에는 각 눈덩이 i (1 ≤ i ≤ N)의 지름을 의미하는 정수 Hi (1 ≤ Hi ≤ 109)가 공백으로 구분되어 주어진다.

 

출력

만들 수 있는 두 눈사람의 키 차이 중 최솟값을 나타내는 정수를 출력하라.

====

문제 풀이

우선 합을 만들 수 있는 모든 경우의 수를 sums라는 배열에 담아준다. 이 때 sums의 요소에는 [합,i인덱스,j인덱스] 까지 담아준다.

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = +input[0];
const arr = input[1].split(' ').map(Number);

const sums = [];
for (let i = 0; i < n - 1; i++) {
    for (let j = i + 1; j < n; j++) {
        const value = arr[i] + arr[j];
        sums.push([value, i, j]);
    }
}

이후 sums를 오름차순으로 정렬한다. 정렬하는 이유는 현재 요소의 합과 제일 가까운 수는 다음 요소의 합이기 때문이다.

sums.sort((a, b) => {
    return a[0] - b[0];
});

이제 첫번째 요소부터 탐색을 진행 할건데 만약 다음으로 탐색한 요소의 i 또는 j가 현재 요소의 i와 j와 겹치면 안되니 이것은 예외처리 해야한다. 이 예외에서 벗어난다면 가장 가까운 수이므로 정답으로 출력할 diff와 비교하여서 더 작은 값을 기록한 뒤 출력하면 된다.

let diff = Infinity;

for (let i = 0; i < sums.length - 1; i++) {
    const [v, x, y] = sums[i];
    const cor = [x, y];
    let j = i + 1;

    while (j < sums.length) {
        const [nv, nx, ny] = sums[j];
        if (!cor.includes(nx) && !cor.includes(ny)) {
            diff = Math.min(diff, nv - v);
            break;
        }
        j++;
    }
}

console.log(diff);

정답 코드

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = +input[0];
const arr = input[1].split(' ').map(Number);

const sums = [];
for (let i = 0; i < n - 1; i++) {
    for (let j = i + 1; j < n; j++) {
        const value = arr[i] + arr[j];
        sums.push([value, i, j]);
    }
}
sums.sort((a, b) => {
    return a[0] - b[0];
});

let diff = Infinity;

for (let i = 0; i < sums.length - 1; i++) {
    const [v, x, y] = sums[i];
    const cor = [x, y];
    let j = i + 1;

    while (j < sums.length) {
        const [nv, nx, ny] = sums[j];
        if (!cor.includes(nx) && !cor.includes(ny)) {
            diff = Math.min(diff, nv - v);
            break;
        }
        j++;
    }
}

console.log(diff);

 

 

diff = 무한대;

for (i = 0; i <sums.length -1; i ++) {
const [v, x, y] = sums [i];
const cor = [x, y];
j = i + 1을하자;

while (j <sums.length) {
const [nv, nx, ny] = 합 [j];
if (! cor.includes (nx) &&! cor.includes (ny)) {
diff = math.min (diff, nv -v);
부서지다;
}
J ++;
}
}

Console.log (diff);