Funcia
Lv.1mathprefix-sumsorting

모든 집 사이 거리의 합

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

일직선 도로 위에 집 n채가 있고, 각 집의 위치가 배열 houses로 주어집니다. 위치는 정렬되어 있지 않으며, 같은 위치에 여러 집이 있을 수도 있습니다.

서로 다른 두 집으로 이루어진 모든 쌍에 대해 두 집 사이의 거리 |houses[i] - houses[j]|(i < j)를 구하고, 그 거리들의 합을 반환하세요.

입출력 예

housesresult
[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

제한 사항

  • 2≤2 \le houses.length ≤200,000\le 200{,}000
  • 0≤0 \le houses[i] ≤108\le 10^8
  • 답은 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번째 집과 그 앞의 모든 집 사이 거리의 합은

(xj−x0)+(xj−x1)+⋯+(xj−xj−1)=j⋅xj−(x0+⋯+xj−1)(x_j - x_0) + (x_j - x_1) + \dots + (x_j - x_{j-1}) = j \cdot x_j - (x_0 + \dots + x_{j-1})

입니다. 앞쪽 위치의 합을 누적하면서 이 값을 더하면 됩니다. 합은 101810^{18} 가까이 커질 수 있으니 64비트 정수로 계산하세요.

복잡도 목표

모든 쌍의 거리를 직접 더하면 O(N2)O(N^2)으로 시간 초과입니다. 정렬과 누적 합으로 O(Nlog⁡N)O(N \log N)에 풀 수 있습니다.

언어별 시간 제한

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

테스트 그룹

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

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