Funcia
Lv.3divide-and-conquerfenwick-treesorting

뒤집힌 쌍 세기

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

정수 배열 nums가 주어집니다. i < j인데 nums[i] > nums[j]인 인덱스 쌍 (i, j)를 뒤집힌 쌍이라고 합니다.

뒤집힌 쌍의 개수를 반환하세요. 값이 같은 두 원소는 뒤집힌 쌍이 아닙니다.

입출력 예

numsresult
[2, 4, 1, 3, 5]3
[5, 4, 3, 2, 1]10
[7, 7, 7]0

입출력 예 설명

예 1 — (2, 1), (4, 1), (4, 3) 세 쌍입니다.

예 2 — 완전히 거꾸로 정렬돼 있어 모든 쌍 (52)=10\binom{5}{2} = 10개가 뒤집혀 있습니다.

예 3 — 같은 값끼리는 뒤집힌 쌍이 아닙니다.

효율성

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

함수 시그니처

solution(nums: int[]) → long

제한 사항

  • 1≤1 \le nums.length ≤200,000\le 200{,}000
  • −109≤-10^9 \le nums[i] ≤109\le 10^9
  • 답은 최대 약 2×10102 \times 10^{10}이라 32비트 정수를 넘을 수 있습니다.

기대 복잡도

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

입출력 예

nums기대 출력
[2,4,1,3,5]3
[5,4,3,2,1]10
[7,7,7]0

힌트

힌트

대표적인 방법이 두 가지 있습니다.

1. 병합 정렬 — 배열을 반으로 나눠 각각 정렬하면서 센 다음, 두 반쪽을 합칠 때 생기는 쌍을 셉니다. 합치는 도중 오른쪽 원소 R[j]를 먼저 내보낸다면, 왼쪽에 아직 남아 있는 원소는 모두 R[j]보다 크므로 그 개수만큼 더합니다. 같은 값이면 왼쪽을 먼저 내보내야 같은 값을 뒤집힌 쌍으로 세지 않습니다.

2. 펜윅 트리(BIT) — 왼쪽부터 보면서, 지금 원소보다 큰 값이 앞에 몇 개 나왔는지를 셉니다. 값의 범위가 넓으니 먼저 정렬해서 순위로 바꾸는 좌표 압축이 필요합니다.

어느 쪽이든 개수는 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 251164 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

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

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