알고리즘/삼성 Certi
[SWEA 3998] Inversion Counting - C++
SangJunni
2025. 2. 26. 09:58
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
문제
길이 N의 수열 A가 주어진다. A의 원소들을 각각 A[1], A[2], ... , A[N]이라고 할 때 i < j 인데 A[i] > A[j] 라면 (A[i], A[j])를 Inversion이라고 한다. (단, 1 ≤ i < j ≤ N)
주어진 순열에서 Inversion의 수를 구하는 프로그램을 작성하라.
입력
첫 줄에 테스트케이스의 개수 T가 주어진다. (T ≤ 20)
입력은 여러개의 테스트 케이스로 이루어져 있으며 테스트 케이스의 개수가 첫 줄에 주어진다. 각 테스트 케이스는 총 2줄로 구성되어있으며,
첫 줄에는 순열의 길이를 나타내는 수 N(2 ≤ N ≤ 100,000)이 주어진다.
다음 줄에는 N개의 수가 공백으로 구분되어 주어지며 이는 순열을 의미한다. 즉, 1부터 N까지의 수가 한번씩 주어진다.
풀이
#include <iostream>
using namespace std;
int input[100001];
int temp[100001];
long long answer;
void mergesort(int start, int end)
{
int mid;
if (start < end)
{
mid = (start + end) / 2;
mergesort(start, mid);
mergesort(mid + 1, end);
int left = start, right = mid + 1, idx = start;
while (left <= mid || right <= end)
{
if (right > end || (left <= mid && input[left] < input[right]))
{
temp[idx] = input[left];
left += 1;
idx += 1;
}
else
{
answer += (mid - left + 1);
temp[idx] = input[right];
right += 1;
idx += 1;
}
}
for (int i = start; i <= end; i++)
{
input[i] = temp[i];
}
}
}
int main(int argc, char** argv)
{
int test_case;
int T;
//freopen("input.txt", "r", stdin);
cin >> T;
for (test_case = 1; test_case <= T; ++test_case)
{
int N;
answer = 0;
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> input[i];
}
mergesort(0, N - 1);
cout << "#" << test_case << " " << answer << endl;
}
return 0;//정상종료시 반드시 0을 리턴해야합니다.
}
해결방법
조건에서 설명한 Inversion 상태를 찾기 위해서 병합 정렬을 활용하면 됩니다.
병합 정렬 수행 (mergesort 함수)
- 재귀적으로 배열을 반으로 나눈 후, 각각을 정렬하여 병합합니다.
- 병합하는 과정에서 역순 쌍을 카운트합니다.
- 역순 쌍이 발생하는 경우는 왼쪽 부분 배열의 값이 오른쪽 부분 배열의 값보다 큰 경우입니다.
- 이때, 왼쪽 배열의 현재 위치에서 끝까지 남은 모든 원소가 현재 오른쪽 값보다 크므로 (mid - left + 1)개 만큼 역순 쌍이 존재합니다.