🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs
.readFileSync(path)
.toString()
.trim()
.split('\r\n')[1]
.split(' ')
.map(BigInt);
const liquid = inputs.sort((a, b) => (a > b ? 1 : -1));
let left = 0;
let right = liquid.length - 1;
let minDiff = 2000000000n;
const ans = [0, 0];
while (left < right) {
let sum = liquid[left] + liquid[right];
sum = sum > 0 ? sum : -1n * sum;
if (sum < minDiff) {
ans[0] = liquid[left];
ans[1] = liquid[right];
minDiff = sum;
}
sum = liquid[left] + liquid[right];
if (sum > 0) right -= 1;
else if (sum < 0) left += 1;
else break;
}
console.log(ans[0].toString(), ans[1].toString());
🟢 풀이
⏰ 소요한 시간 : -
투 포인터 유형의 문제이다. 투포인터를 모른다면 해당 게시물을 통해 투포인터 알고리즘을 먼저 학습해야 한다.
용액 특성 값은 -1,000,000,000 ~ 1,000,000,000 의 범위를 가지므로 BigInt 형태로 풀이를 진행해야 한다. sort 함수를 사용해서 정렬을 해줘야 한다.
이 때 sort 함수의 명세중 내부의 콜백함수에 대한 명세를 보면 다음과 같다.
콜백함수 comparator가 정의 되어 있을 때, comparator를 호출하고 그 결과인 v를 반환하도록 되어 있다. 반환값 v는 ToNumber함수를 통해 숫자인지 확인하는 과정을 거치는데 ToNumber 함수 내부의 2번 명세를 보면 BigInt일 경우 TypeError를 던진다고 한다.
따라서 리턴값은 명백한 number 타입이여야 하므로 sort((a,b) => a-b) 가 아닌 sort((a, b) => (a > b ? 1 : -1))로 리턴값을 직접 명시해준다.
정렬된 값들은 liquid라는 배열에 넣어두고 투포인터를 수행한다.
첫 번째 요소와 마지막 요소를 left, right로 명시한 뒤 left 가 right 보다 커질때까지 반복을 수행한다.
이때 두 합의 절대값이 최소 절대값인지 확인하는 과정을 거친다. 만약 두 값이 최소 절대값이라면 정답 배열을 현재 타겟값인 liquid[left]와 liquid[right]로 업데이트 해주고 최소 절대값 또한 업데이트 해준다.
최소 절대값을 만난것과 별개로 두개의 포인터 값을 변경시키며 다음 값을 확인하며 투포인터를 진행한다.
이때 두 용액의 합이 0이라면 더 이상 비교를 할 필요가 없다. 답은 여러개일 수 있고 그 중 하나의 값만 출력하면 되기 때문이다.
마지막 정답을 출력하기 전에는 toString() 메서드를 통해 문자열로 변경해서 출력하기
🔵 Ref
