[백준] 2141번: 우체국 (JavaScript, NodeJS)

문제

수직선과 같은 일직선상에 N개의 마을이 위치해 있다. i번째 마을은 X[i]에 위치해 있으며, A[i]명의 사람이 살고 있다.

이 마을들을 위해서 우체국을 하나 세우려고 하는데, 그 위치를 어느 곳으로 할지를 현재 고민 중이다. 고민 끝에 나라에서는 각 사람들까지의 거리의 합이 최소가 되는 위치에 우체국을 세우기로 결정하였다. 우체국을 세울 위치를 구하는 프로그램을 작성하시오.

각 마을까지의 거리의 합이 아니라, 각 사람까지의 거리의 합임에 유의한다

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다.

출력

첫째 줄에 우체국의 위치를 출력한다. 가능한 경우가 여러 가지인 경우에는 더 작은 위치를 출력하도록 한다.

예제 입력 1 복사

3
1 3
2 5
3 3

예제 출력 1 복사

2

정답 풀이

const path = process.platform === "linux" ? "/dev/stdin" : "input.txt"; // 리눅스로 테스트할 땐 따로 설정해주어야 합니다.
const input = require("fs").readFileSync(path).toString().trim().split("\n");

let [n, ...arr] = input;
const cityAndPeople = arr.map(i => i.split(' ').map(j => +j));

// 문제 풀이:
function solution(n, cityAndPeople) {
	// 마을 번호를 오름차순 정렬한다.
	cityAndPeople.sort((a, b) => a[0] - b[0]);

	// 각 마을에 있는 인구수를 전부 합쳐서 변수에 저장한다.
	const peopleCount = cityAndPeople.reduce((acc, cur) => acc + cur[1], 0);
	let sum = 0;

	// 마을을 돌면서, 전체 인구수의 절반을 넘거나 같은 지점이 우체국을 놓는 지점이다.
	for (let i = 0; i < n; i += 1) {
		sum += cityAndPeople[i][1];
		if (peopleCount / 2 <= sum) return cityAndPeople[i][0];
	}

	return cityAndPeople[cityAndPeople.length - 1][0];
}

// 제출
const answer = solution(n, cityAndPeople);
console.log(answer);

⭐ 문제 핵심 아이디어 ⭐
1. 그리디
2. 인구수의 절반을 넘는 지점이 우체국을 놓을 위치
3. 두 곳의 지점에 놓을 수 있다면 낮은 곳이 정답
4. 마을 번호가 정렬이 안돼서 들어오는 것도 생각

인구수의 절반을 넘는 지점을 찾는다

라는 아이디어를 얻지 못했다..

검색을 통해서 얻었는데

그리디는 잘 풀리는 문제는 바로 풀리는데

풀리지 않는 문제는 아무리 생각을 해도 풀리지 않는다.

하나의 생각에 꽂혀버리면 다른 생각을 잘 하지 못하는 것 같다.

생각을 넓히는 것이 중요한 것 같다.

 

잘 안풀릴 때 아래의 반례를 해결해보세요.

2
1 1
2 1