서로 다른(distinct) 정수로 이루어진 정렬되지 않은 배열이 주어집니다. 목표는 배열을 정렬했을 때 발생하는 교차 선(cross line)의 개수를 구하는 것입니다. 교차 선은 아래 그림과 같이 계산됩니다.
Arr[] = { 1, 2, 4, 3, 5 } → 아래 그림과 같이 교차 선이 3개 존재합니다.
Arr[] = { 1, 2, 3, 4, 5 } → 이미 정렬된 상태이므로 교차 선이 하나도 없습니다.
이 문제는 사실 역전(inversion) 쌍의 개수를 세는 문제와 본질적으로 같습니다. 값의 순서가 뒤바긴 원소 쌍만큼 선이 서로 교차하기 때문입니다. 여기서는 삽입 정렬(insertion sort)을 활용해 교차 선의 개수를 셉니다. 삽입 정렬은 오른쪽의 원소를 왼쪽의 정렬된 구간에 하나씩 끼워 넣는 방식으로 동작하는데, 새 원소가 자신의 올바른 위치로 이동할 때마다 카운트를 증가시키면 됩니다. 원소가 이동하는 동안 자신보다 큰 모든 원소를 가로지르며 지나가므로, 지나간 원소의 수가 곧 교차 선의 개수가 됩니다.
예제로 이해하기
입력 − arr[] = { 4, 3, 1, 2 }
출력 − 배열의 교차 선 개수 − 5
설명 − 선 4-4와 3-3이 선 1-1과 2-2와 각각 교차합니다. 여기까지 총 4개의 교차 선이 발생합니다.
또한 4-4와 3-3은 서로 한 번 교차하므로, 전체 교차 선은 4 + 1 = 5개입니다.
입력 − arr[] = { 0, 1, 5, 3 }
출력 − 배열의 교차 선 개수 − 1
설명 − 5-5와 3-3이 서로 한 번 교차합니다. 따라서 교차 선은 총 1개입니다.
프로그램에 사용된 접근 방식
서로 다른 숫자들로 초기화된 정수 배열 arr[]를 준비합니다.
insertionSort(int arr[], int n) 함수는 배열과 배열의 길이를 입력받아, 정렬을 수행한 뒤 교차 선의 개수를 결과로 반환합니다.
교차 선의 초기 개수는 0으로 설정하며, count 변수를 사용합니다.
첫 번째 원소는 이미 정렬된 것으로 간주하므로, 두 번째 원소부터 마지막 원소까지(i = 1 ~ i < n) 각 원소를 item에 담습니다(item = arr[i]). 그리고 j = i - 1로 설정합니다.
arr[j]가 item보다 크고 j >= 0인 동안 원소들을 오른쪽으로 한 칸씩 밀어냅니다. 밀어낼 때마다 count를 증가시키는데, 이는 item이 해당 원소들을 모두 가로지르기 때문입니다.
while 루프가 끝나면 item을 올바른 위치인 arr[j + 1]에 배치합니다.
모든 원소에 대해 이 과정을 반복하며, 각 원소가 가로지르는 원소의 수를 셉니다.
최종적으로 count 값이 가능한 교차 선의 총 개수가 됩니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int insertionSort(int arr[], int n){
int count=0;
int item;
int j;
for (int i = 1; i < n; i++){
item = arr[i];
j = i - 1;
//정렬된 구간에서 올바른 위치에 원소를 삽입.
//오른쪽에서 올바른 위치까지 지나간 원소의 수가 곧 교차 선의 개수.
while (j >= 0 && arr[j] > item){
arr[j + 1] = arr[j];
j = j - 1;
count++;
}
arr[j + 1] = item;
}
return count;
}
int main(){
int arr[] = { 4,5,3,1,2};
int n = 5;
cout<<"Number of cross lines: "<<insertionSort(arr, n);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Number of cross lines: 8
복잡도 분석
삽입 정렬 기반 접근의 시간 복잡도는 최악의 경우 O(n²)입니다. 배열이 거꾸로 정렬된 경우 모든 원소 쌍이 서로 교차하게 되어 연산량이 가장 많아집니다. 따라서 입력 크기가 클 때는 병합 정렬을 응용해 O(n log n) 시간에 역전(교차 선) 개수를 세는 방식을 사용하는 것이 효율적입니다.