문제
마법사 N명이 머글 문화를 이해하기 위해 머글과 약속을 잡았다. 각 마법사는 한 명의 머글을 만날 예정이다. 하지만, 마법사는 약속 시간보다 빨리 또는 늦게 도착할 수 있기 때문에 고민에 빠졌다. 결국 기다리는 시간을 최소화 하기 위해 모든 약속 시간을 T씩 미루려고 한다. 기다리는 시간은 먼저 도착한 사람이 늦게 도착한 사람이 도착할 때까지 기다리는 시간을 의미한다.
마법사의 약속 시간은 A1, A2, ..., AN이고, 도착 시간은 B1, B2, ..., BN이다. 약속 시간을 T만큼 미루면, 기다리는 시간의 합은 |Ai + T - Bi|의 합과 같다. 기다리는 시간의 합이 최소가 되는 서로 다른 정수 T의 개수를 구해보자.
1 ≤ N ≤ 50
1 ≤ Ai, Bi ≤ 109
입력
첫째 줄에 N이 주어진다. 다음 N개의 줄에 Ai, Bi가 주어진다.
출력
첫째 줄에 기다리는 시간의 합이 최소인 서로 다른 정수 T의 개수를 출력한다.
예제 입력
2
20 18
30 25
예제 출력
4
내가 했던 풀이 방법
이번 코드는 수학적인 지식이 필요하다. 물론 없어도 구현은 가능하지만, 시간초과가 발생하게 될 것이다. 처음 문제를 보고 풀이한 방법은 diff의 최소 최대를 구해서 최소부터 최대까지 각각 기다리는 시간의 합을 구해서 가장 작을 때의 개수를 출력해주었는데, 값은 잘 나왔지만 시간초과가 발생했다.
실제 정답도 유사하게 풀이가 되지만 조금 더 수학적으로 지식이 필요하다. 일단 수학을 굉장히 못하기 때문에 필자도 이해할 수 있는 수준에서 간단하게만 정리한다.
조금 간단한 수식으로 먼저 알아보면, 여기서 a_i는 수열의 각 원소를 나타내고, x는 선택할 값일 때, f(x)를 최소화하는 x 값을 찾아야 한다. 여기서 절댓값 합을 최소화하는 값은 수열의 중앙값(median) 이다. 중앙값은 전체 값들을 정렬한 후에 가운데 위치한 값입니다. 중간값을 기준으로 양쪽의 값들이 상쇄되기 때문에 중앙값이 최소가 될 수 있다.
즉, 아래의 내용을 알 수 있게 된다.
수열의 길이가 홀수일 경우: 정렬된 수열의 가운데 값이 중앙값
수열의 길이가 짝수일 경우: 가운데 두 값 사이 어느 값을 선택해도 절댓값 합이 최소화
이제 우리 문제에서 의도한 내용으로 생각해보면, 이 수식을 아래와 같이 변형할 수 있다.
즉, Ai-Bi를 하나의 수열로 두고, (약속시간-도착시간)+미룰시간이 최소가 될 때를 찾으면 된다. 더 쉽게 말하면 각각의 약속시간-도착시간의 중앙값을 찾아주면 된다.
코드를 설명해보면,
N이 홀수일 때는 1을 출력해주고, 짝수일 경우에는 입력받은 약속/도착 시간의 차이를 diff에 저장해준다. diff를 오름차순으로 정렬해주고 중앙값(min/max는 중앙값 중 크고 작은 값을 의미한다)을 찾아준다. 해당 값 사이에 있는 값들이 모두 가능하므로 max-min+1을 출력해준다.
코드
const fs = require('fs');
let [N, ...time] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');
N = Number(N);
let promise = Array.from({ length: N }, () => null);
let arrive = Array.from({ length: N }, () => null);
let diff = [];
if (N % 2 !== 0) console.log(1);
else {
for (let i = 0; i < N; i++) {
let [time1, time2] = time[i].trim().split(' ').map(Number);
promise[i] = time1;
arrive[i] = time2;
diff.push(promise[i] - arrive[i]);
}
diff.sort((a, b) => a - b);
let min = diff[Math.floor(diff.length / 2) - 1];
let max = diff[Math.floor(diff.length / 2)];
console.log(max - min + 1);
}회고
생각하는 것까지는 얼추 따라갔는데 모든 값들을 다 계산해버려서 문제였다. 처음 문제를 보고 메모장에 적으면서 -1/+1씩 변하고 있어서 규칙을 발견했을 법 했는데 그 부분까지 생각을 못한 것 같다.. 그래도 처음 풀이가 완전히 틀린 건 아니였다는 것에 의의를 둔다!
참고자료
