해당 포스팅은 백준 2230번 수 고르기 풀이를 다룬다. 문제 링크
코드는 Javascript로 작성하였다.
문제
문제 설명
N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.
예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.
입력
첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다.
출력
첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.
풀이
주어진 수열을 정렬한 후 투포인터를 이용해 최솟값을 찾으면 되는 문제이다.
주어진 수열을 정렬한다. 정렬된 수열 nums에 대해 투포인터를 이용해 nums[e] - nums[s] >= M을 만족하는 최솟값 sub을 찾아야 한다. 만약 sub이 m일 경우 문제에서 요구하는 최솟값이므로 즉시 리턴시킬 수 있다.
비슷한 문제로 백준의 나무자르기 문제가 있다.
예제 분석
예제 1
[input]
- 수열: {1, 2, 3, 4, 5}
- M: 3
[ouput]: 3
1 4, 1 5, 2 5를 골랐을 때 M인 3이상이 된다. 가장 최솟값인 3을 리턴한다.
예제2
[input]
- 수열: {1, 5, 3}
- M: 3
[outpur]: 4
1 5를 골랐을 때 M인 3이상인 4가 된다. 따라서 4를 리턴한다.
추가 케이스 분석
예제3
[input]
- 수열: {1, 2, 3, 5, 6}
- M: 3
[outpur]: 3
1 5, 1 6, 2 5, 2 6, 3 6을 골랐을 때 M인 3이상이 된다. 가장 최솟값인 3을 리턴한다.
Pseudo Code
주어진 수열(nums)을 정렬한다.
투포인터 s, e = 0;
정답 answer = 0;
// 수열 길이만큼 탐색하기 위해 반복문을 돌린다.
while (s <= e and e < n)
두 값의 차이 sub = nums[e] - nums[s];
if (sub < m) 값을 늘려주기 위해 e += 1;
if (sub > m)
// m 이상이긴 하지만 최솟값을 구해주어야 하므로 업데이트
answer = Math.min(answer, sub);
값을 줄여주기 위해 s += 1;
if (sub === e)
가능한 최솟값이므로 return m;
return answer;전체 코드
const input = require('fs').readFileSync('/dev/stdin').toString().split('\n').slice(0, -1);
const nm = input.shift().split(" ");
const [n,m] = nm.map(el => Number(el));
const parsed = input.map(el => Number(el));
function solution(n,m,arr) {
const nums = arr.sort((a,b) => a-b);
let s = e = 0;
let ans = Number.MAX_VALUE;
while (s <= e && e < n) {
const sub = nums[e] - nums[s];
if (sub < m) {
e += 1;
continue;
}
if (sub === m) {
return m;
}
ans = Math.min(ans, sub);
s += 1;
}
return ans;
}
console.log(solution(n,m,parsed));