백준_20366_같이 눈사람 만들래?

Minji Lee·2025년 4월 24일

20366 js 같이 눈사람 만들래?백준

JS코딩테스트

목록 보기

111/122

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

5
3 5 2 5 9

예제 출력 1

풀이 및 해설

출력값: 엘자와 안나가 각각 눈사람을 만들 때, 눈사람의 키 차이의 최솟값 구하기
눈사람 키 = 아래 눈덩이 + 위 눈덩이
위 눈덩이는 아래 눈덩이보다 크지 않아야함

엘자가 먼저 눈덩이 선택하기(선택한 눈덩이 표시)
엘자가 선택한 눈덩이를 제외한 나머지 눈덩이들 배열 만들기
안나는 나머지 눈덩이들 중 2개 선택하기(이때, 투포인터 이용)
a. 맨 앞 인덱스(start)와 맨 끝 인덱스(end)부터 시작
b. 안나의 눈덩이 키 < 엘자 눈덩이 키 → start 인덱스 + 1
c. 안나의 눈덩이 키 > 엘자 눈덩이 키 → end 인덱스 - 1
d. 두 눈덩이 키가 같으면 → 가장 작은 값인 0이므로 바로 0 리턴

Code

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input[0]; // 눈덩이 개수 N
const diameters = input[1].split(' ').map(Number); // 각 눈덩이의 지름
diameters.sort((a, b) => a - b); // 눈덩이 오름차순 정렬

const isUsed = Array.from({ length: N }, () => false); // 엘사가 선택한 눈덩이

let result = Number.MAX_SAFE_INTEGER;
const selectAnna = (elsaSize) => {
  const remains = diameters.filter((_, index) => !isUsed[index]);
  let [start, end] = [0, remains.length - 1];
  while (start < end) {
    const annaSize = remains[start] + remains[end];
    result = Math.min(result, Math.abs(elsaSize - annaSize));
    if (elsaSize > annaSize) start += 1;
    else if (elsaSize < annaSize) end -= 1;
    else return false;
  }
  return true;
};

// 엘사가 눈덩이 두 개 선택하는 경우
for (let i = 0; i < N; i++) {
  isUsed[i] = true;
  for (let j = i + 1; j < N; j++) {
    isUsed[j] = true;
    if (!selectAnna(diameters[i] + diameters[j])) return console.log(result);
    isUsed[j] = false;
  }
  isUsed[i] = false;
}

console.log(result);

시간 개선하기

엘사가 선택한 눈덩이 제외한 나머지 눈덩이 배열 만드는 과정 없애기

const remains = diameters.filter((_, index) => !isUsed[index]);

→ 안나가 눈덩이 선택할 때, 엘사가 선택한 눈덩이인 경우 패스

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input[0]; // 눈덩이 개수 N
const diameters = input[1].split(' ').map(Number); // 각 눈덩이의 지름
diameters.sort((a, b) => a - b); // 눈덩이 오름차순 정렬

let result = Number.MAX_SAFE_INTEGER;

for (let i = 0; i < N; i++) {
  for (let j = i + 1; j < N; j++) {
    const elsaSize = diameters[i] + diameters[j]; // 엘자가 눈덩이 두 개 먼저 선택

    let [start, end] = [0, N - 1];
    while (start < end) {
      // 안나가 엘자가 선택한 눈덩이 고른 경우 다른 눈덩이 선택
      if (start === i || start === j) {
        start++;
        continue;
      }
      if (end === i || end === j) {
        end--;
        continue;
      }

      const annaSize = diameters[start] + diameters[end];
      result = Math.min(result, Math.abs(elsaSize - annaSize));
      if (elsaSize > annaSize) start += 1;
      else if (elsaSize < annaSize) end -= 1;
      else return console.log(result); // 두 눈덩이 키가 같은 경우 바로 0 리턴
    }
  }
}

console.log(result);