Lv.1mathprefix-sumsorting
모든 집 사이 거리의 합
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
일직선 도로 위에 집 n채가 있고, 각 집의 위치가 배열 houses로 주어집니다. 위치는 정렬되어 있지 않으며, 같은 위치에 여러 집이 있을 수도 있습니다.
서로 다른 두 집으로 이루어진 모든 쌍에 대해 두 집 사이의 거리 |houses[i] - houses[j]|(i < j)를 구하고, 그 거리들의 합을 반환하세요.
입출력 예
| houses | result |
|---|---|
[1, 3, 6] | 10 |
[5, 5, 5] | 0 |
[8, 0, 2, 2] | 24 |
입출력 예 설명
예 1 — 쌍별 거리는 |1 - 3| = 2, |1 - 6| = 5, |3 - 6| = 3이고 합은 10입니다.
예 2 — 모든 집이 같은 위치에 있어 거리가 모두 0입니다.
예 3 — 쌍별 거리는 8(8과 0), 6(8과 첫 번째 2), 6(8과 두 번째 2), 2, 2(0과 각 2), 0(2와 2)이고 합은 24입니다. 같은 위치의 두 집도 서로 다른 쌍으로 셉니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(houses: int[]) → long
제한 사항
-
houses.length -
houses[i] - 답은 32비트 정수 범위를 넘을 수 있습니다. 64비트 정수(
long)를 사용하세요.
기대 복잡도
- 시간
- O(N log N)
- 공간
- O(N)
입출력 예
| houses | 기대 출력 |
|---|---|
[1,3,6] | 10 |
[5,5,5] | 0 |
[8,0,2,2] | 24 |
힌트
힌트
쌍의 순서는 답에 영향을 주지 않으므로 먼저 위치를 오름차순으로 정렬하세요. 정렬된 배열 x에서 j번째 집과 그 앞의 모든 집 사이 거리의 합은
입니다. 앞쪽 위치의 합을 누적하면서 이 값을 더하면 됩니다. 합은 가까이 커질 수 있으니 64비트 정수로 계산하세요.
복잡도 목표
모든 쌍의 거리를 직접 더하면 으로 시간 초과입니다. 정렬과 누적 합으로 에 풀 수 있습니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1186 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 4 | 판정만 |