앞지른 쌍 개수 세기
자바스크립트 코딩테스트 문제로 inversion-count 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
앞에 있어야 할 큰 수가 뒤의 더 작은 수보다 먼저 나타나는 쌍이 몇 개인지 세어 보는 문제입니다.
문제 설명
정수 배열 nums가 주어질 때, 인덱스 i < j를 만족하면서 nums[i] > nums[j]인 쌍의 개수를 반환하는 countOutOfOrderPairs 함수를 작성하세요.
이런 쌍은 배열이 정렬 기준에서 얼마나 뒤섞여 있는지 보여 주는 대표적인 지표입니다.
예를 들어 [3, 1, 2]에서는 (3, 1), (3, 2) 두 쌍이 조건을 만족하므로 정답은 2입니다.
제한사항
1 <= nums.length <= 200000-1000000000 <= nums[i] <= 1000000000- 같은 값이 여러 번 등장할 수 있습니다.
- 같은 값끼리는 역전 쌍으로 세지 않습니다.
- 반환값은 JavaScript의 안전한 정수 범위 안에 들어온다고 가정합니다.
예시
- 입력:
[3, 1, 2]→ 출력:2 - 입력:
[1, 2, 3, 4]→ 출력:0 - 입력:
[4, 3, 2, 1]→ 출력:6 - 입력:
[2, 2, 1, 1]→ 출력:4
힌트
- 모든
(i, j)를 직접 비교하면O(n^2)이라 길이가 큰 배열에서는 너무 느립니다. - 배열을 반으로 나눈 뒤, 왼쪽 내부 / 오른쪽 내부 / 양쪽을 가로지르는 쌍으로 나눠 생각해 보세요.
- 정렬된 두 구간을 병합할 때 오른쪽 값이 먼저 나왔다면, 그 값보다 아직 남아 있는 왼쪽 값들은 모두 역전 쌍을 만듭니다.
해설
이 문제는 merge sort를 이용한 inversion count의 대표 예시입니다.
핵심은 역전 쌍을 세면서 동시에 배열을 정렬하는 것입니다.
1. 역전 쌍을 세는 위치를 나눕니다
배열을 절반으로 나누면 역전 쌍은 세 종류로 나뉩니다.
- 왼쪽 절반 안에서만 생기는 쌍
- 오른쪽 절반 안에서만 생기는 쌍
- 왼쪽 절반의 원소와 오른쪽 절반의 원소가 만드는 쌍
1번과 2번은 재귀적으로 같은 방식으로 셀 수 있습니다. 남는 핵심은 3번, 즉 가로지르는 역전 쌍입니다.
2. 병합 과정에서 가로지르는 역전 쌍을 셉니다
merge sort처럼 왼쪽 구간과 오른쪽 구간이 이미 각각 정렬되어 있다고 가정해 봅시다.
- 왼쪽:
[1, 4, 7] - 오른쪽:
[2, 5, 6]
두 포인터로 병합할 때 1과 2를 비교하면 1 <= 2이므로 1을 먼저 넣습니다.
그다음 4와 2를 비교하면 4 > 2입니다.
이 순간 중요한 사실이 있습니다.
왼쪽 구간은 이미 정렬되어 있으므로, 현재 4뿐 아니라 그 뒤의 7도 모두 2보다 큽니다.
즉 2는 남아 있는 왼쪽 원소 개수만큼 역전 쌍을 한 번에 만듭니다.
그래서 rightValue < leftValue가 되는 순간마다
왼쪽에 아직 남아 있는 원소 수 = mid - leftPointer + 1을 더하면 됩니다.
3. 같은 값은 세지 않도록 주의합니다
문제 조건은 nums[i] > nums[j]일 때만 세는 것입니다.
즉 값이 같으면 역전 쌍이 아닙니다.
그래서 병합 시 leftValue <= rightValue인 경우에는 왼쪽 값을 먼저 넣어야 중복값이 잘못 세어지지 않습니다.
예를 들어 [2, 2, 1, 1]에서는 각 2가 뒤의 각 1과만 역전 쌍을 이루므로 총 4개입니다.
같은 값끼리는 세면 안 됩니다.
4. 왜 이 풀이가 빠를까요?
배열을 계속 반으로 나누고, 각 단계에서 병합은 선형 시간에 끝납니다.
- 분할 깊이:
O(log n) - 각 깊이에서 병합 총합:
O(n)
따라서 전체 시간 복잡도는 O(n log n)입니다.
n이 200000까지 커져도 충분히 통과할 수 있습니다.
알고리즘별 코테 관점에서는 분할 정복 + 정렬 과정에서 추가 정보를 함께 세는 감각을 익히기 좋은 문제입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.