Lv.1mathsorting
우체국 위치 정하기
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 정답률
- 100.0%
- 푼 사람
- 1
일직선 도로 위에 집들이 있고, houses[i]는 i번째 집의 좌표입니다. 같은 좌표에 집이 여러 채 있을 수 있습니다.
도로 위의 정수 좌표 한 곳에 우체국을 지으려고 합니다. 모든 집에서 우체국까지의 거리의 합이 가장 작아지도록 지었을 때, 그 거리 합을 반환하세요.
입출력 예
| houses | result |
|---|---|
[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
제한 사항
-
houses.length -
houses[i] - 답은 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/퀵셀렉트를 쓰면 정렬 없이 에도 됩니다. 거리 합은 64비트 정수로 더하세요.
복잡도 목표
집 위치마다 거리 합을 다시 계산하는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1302 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 7 | 판정만 |
| performance | 60 | 4 | 판정만 |