[백준 2285번] 파이썬 - 우체국

백준 2285 - 우체국

시간 제한 2초, 메모리 제한 128MB

# 조건

• 수직선과 같은 일직선상에 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 이며 모든 입력은 정수이다.
• 모든 A[i]를 합친 값은 0보다 크다.

출력

• 첫째 줄에 우체국의 위치를 출력한다.
• 단, 답이 여러 개일 경우 우체국의 위치가 작은 것을 출력한다.

# 접근 방법

• 주어지는 N개의 마을과 마지막 마을 번호가 일치하는 것이 아니기 때문에 리스트의 크기를 마을 번호로 한다면 메모리 초과가 발생한다.
  • 10억까지의 번호가 존재할 수 있으므로!!
• 우선 마을 번호와 사람의 수를 받은 후, 마을 번호를 기준으로 오름차순 정렬해준다.
• 이후, 마을 개수 크기의 리스트를 생성 후 누적합을 구해준다.
• 이제 우체국을 마을마다 세우면서 최소 거리가 되는 곳을 찾아주면 되는데
  • 현재 마을에 우체국을 세운 경우 좌우의 인구 수의 차이가 가장 작은 곳이 우체국을 세워야 되는 곳이다.
  • 전체 인구의 절반이 넘어가는 시점이 모든 사람이 이용할 때 최소가 되는 값이기 때문이다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N = int(input())  
town = []  

for _ in range(N):  
    a, b = map(int, input().split())  
    town.append((a, b))  

town.sort()  
people = [0] * len(town)  

for idx, cnt in enumerate(town):  
    people[idx] = cnt[1]  

if N == 1:  
    print(town[0][0])  
    sys.exit(0)  
z_to_n = [0] * N  
z_to_n[0] = people[0]  

for i in range(1, N):  
    z_to_n[i] = z_to_n[i-1] + people[i]  

val = z_to_n[-1] - z_to_n[0]  
result = town[0][0]  
for j in range(1, N):  
    temp = abs(z_to_n[j-1] - (z_to_n[-1] - z_to_n[j]))  
    if temp < val:  
        val = temp  
        result = j  
print(town[result][0])