[백준] 20300번 : 서강근육맨

문제

출처 : https://www.acmicpc.net/problem/20300

로니 콜먼 동영상을 보고 보디빌더가 되기로 결심한 향빈이는 PT 상담을 받으러 서강헬스클럽에 갔다. 향빈이가 서강헬스클럽을 선택한 이유는 PT를 받을 때 사용하는 운동기구를 회원이 선택할 수 있다는 점 때문이다. 하지만, 서강헬스클럽은 항상 사람이 많아서 PT를 한 번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다.

헬스장에 있는
$N$개의 운동기구를 한 번씩 사용해보고 싶은 향빈이는 PT를 받을 때마다 이전에 사용하지 않았던 운동기구를 선택하기로 계획을 세웠다. 그리고 비용을 절약하기 위해 PT를 받을 때 운동기구를 되도록이면 두 개를 사용하기로 했다. 예를 들어, 헬스장에 총
$10$개의 운동기구가 있을 경우 PT를
$5$번 받으면 모든 기구를 다 사용할 수 있다.
$9$개의 운동기구가 있는 경우에도 PT를
$5$번 받지만, 마지막 PT를 받을 때는 운동기구를 하나만 사용한다.

하지만 향빈이는 운동기구를 선택하다가 큰 고민에 빠졌다. 왜냐하면 운동기구마다 근손실이 일어나는 정도가 다르기 때문이다. 어떤 운동기구는 자극이 잘 안 와서 근손실이 적게 일어나는데, 어떤 운동기구는 자극이 잘 와서 근손실이 많이 일어난다. 근손실이 죽음보다 무서운 향빈이는 PT를 한 번 받을 때의 근손실 정도가
$M$을 넘지 않도록 하고 싶다. 이때,
$M$의 최솟값을 구해보자. 참고로, 운동기구를 두 개 사용해서 PT를 받을 때의 근손실 정도는 두 운동기구의 근손실 정도의 합이다.

입력

첫째 줄에 서강헬스클럽에 비치된 운동기구의 개수를 나타내는 정수
$N$이 주어진다. (
$1 \leq N \leq 10\ 000$)

둘째 줄에는 각 운동기구의 근손실 정도를 나타내는 정수
$t_1, t_2, \cdots, t_N$가 주어진다. (
$0 \leq t_i \leq 10^{18}$)

출력

$M$의 최솟값을 출력한다.

첫번째 시도

const fs = require('fs');
const [count, digits] = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const arr = digits.split(" ").map((el) => Number(el));

arr.sort((a,b) => a - b);

let hardest;

const solution = (arr) => {
    let array = arr;
    if(array.length === 1) {
        return array[0];
    }

    if(array.length % 2 == 1) {
        hardest = array.pop();
    }

    let i = 0;
    let j = array.length -1;
    let result = hardest ? hardest : -Infinity;

    while (i < j) {
        const sum = array[i] + array[j]
        result = Math.max(result, sum);
        i+= 1;
        j-= 1;
    }
    return result;
}

console.log(solution(arr).toString());

긴가민가 했지만 로직 자체는 상당히 쉬웠다. 하지만 어느 곳을 쳐다봐도 예외사항이 없을 것 같은데 계속 틀렸습니다를 내뱉는 것이 아닌가? 이 문제의 숨은 폭탄은 문제 자체에 있었다.

둘째 줄에는 각 운동기구의 근손실 정도를 나타내는 정수
$t_1, t_2, \cdots, t_N$가 주어진다. (
$0 \leq t_i \leq 10^{18}$)

즉, 자바스크립트의 자료형에 $10^{18}$에 해당되는 큰 숫자가 할당된다는 것인데, 일반적인 자바스크립트의 Number로는 이를 감당할 수 없다. 일단 부동소수점을 이용하며, 정수형의 경우 16자리까지밖에 감당할 수 밖에 없다. Number.MAX_SAFE_INTEGER : Number가 나타낼 수 있는 최대의 정수부

이에 정수부를 제한없이 나타내게 하는 데이터 타입인 BigInt가 나오게 되었다. 사용 방법은 그냥 BigInt(숫자) 이렇게 선언하면 되며, 일반적인 Number와는 다르게 뒤에 n이 붙는다. 그렇다고 문자열이 아니라, BigInt라는 자료형이 별도로 부과된다.

그렇다보니 BigInt는 전통적인 자바스크립트의 대소 비교로는 불가하다.

1) sort()

보통 우리는 오름차순으로 배열을 정리하고 싶을 때,

array.sort(() => a - b);

이런 형식으로 사용하곤 한다. 그러나 BigInt는 사실상 사칙연산이 아니라 대소 비교로 사용할 수 있다.

arr.sort((a, b) => (a < b ? -1 : 1));

2) Math.max(), Math.min()

Math를 이용한 단순 비교도 불가하다. 그러므로 대소 비교를 이용해야만 한다.

ex)

const result = BigInt(10);
const target = 15;
const isBigger = result > target ? true : false; 

어쨋든 그래서 BigInt를 이용하여 리팩토링한 것은 다음과 같다.

const fs = require("fs");
let [count,digits] = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let arr = digits.split(" ").map((e) => BigInt(e));

arr.sort((a, b) => (a < b ? -1 : 1));

let hardest;

const solution = (arr) => {
    if(arr.length === 1) {
        return array[0];
    }

    if(arr.length % 2 == 1) {
        hardest = arr.pop();
    }

    let i = 0;
    let j = arr.length -1;
    let result = hardest ? hardest : -Infinity;

    while (i < j) {
        const sum = arr[i] + arr[j]
        result = result > sum ? result : sum;
        i+= 1;
        j-= 1;
    }
    return result;
}

console.log(String(solution(arr));

어떤 분들은 배열에서 shift(), pop() 하면서 줄여나가시던데, 특히 shift()를 하며 리인덱싱이 되기 때문에 직접 빼는 것보단 조회를 하는 편이 훨씬 더 효율적인 것 같다.