Funcia
Lv.1mathsorting

우체국 위치 정하기

메모리 제한
256 MB
정확성 시간 제한
10000 ms
정답률
100.0%
푼 사람
1
0

일직선 도로 위에 집들이 있고, houses[i]는 i번째 집의 좌표입니다. 같은 좌표에 집이 여러 채 있을 수 있습니다.

도로 위의 정수 좌표 한 곳에 우체국을 지으려고 합니다. 모든 집에서 우체국까지의 거리의 합이 가장 작아지도록 지었을 때, 그 거리 합을 반환하세요.

입출력 예

housesresult
[1, 2, 9]8
[5, -3, 5, 10]13
[7]0

입출력 예 설명

예 1 — 좌표 2에 지으면 1 + 0 + 7 = 8입니다.

예 2 — 좌표 5에 지으면 8 + 0 + 0 + 5 = 13입니다. 좌표가 −3, 5, 5, 10인 집들 기준으로 5부터 5 사이 어디든 같습니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(houses: int[]) → long

제한 사항

  • 1≤1 \le houses.length ≤200,000\le 200{,}000
  • −109≤-10^9 \le houses[i] ≤109\le 10^9
  • 답은 32비트 정수를 넘을 수 있습니다.

기대 복잡도

시간
O(N log N)
공간
O(1)

입출력 예

houses기대 출력
[1,2,9]8
[5,-3,5,10]13
[7]0

힌트

힌트

우체국을 오른쪽으로 1 옮기면, 왼쪽에 있는 집들은 거리가 1씩 늘고 오른쪽 집들은 1씩 줄어듭니다. 그러니 왼쪽과 오른쪽 집의 수가 같아지는 곳, 즉 중앙값에서 거리 합이 가장 작습니다.

정렬한 뒤 가운데 원소(houses[n / 2])에 짓고 거리를 더하면 됩니다. 짝수 개면 가운데 두 원소 사이 어디든 답이 같습니다.

nth_element/퀵셀렉트를 쓰면 정렬 없이 O(N)O(N)에도 됩니다. 거리 합은 64비트 정수로 더하세요.

복잡도 목표

집 위치마다 거리 합을 다시 계산하는 O(N2)O(N^2) 풀이는 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251302 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness407판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.