문제 개요
이번 문제에서는 n개의 요소(n은 홀수)를 가진 배열 A를 다룹니다. 배열 A에는 1부터 n까지의 자연수가 순열(permutation) 형태로 들어 있습니다. 또한 함수 f(i)가 정의되어 있는데, 이 함수는 0부터 n-2 범위의 인덱스 i 하나를 인자로 받아 다음 연산을 수행합니다.
- 만약 A[i] > A[i+1]이라면, 두 값을 서로 교환(swap)합니다.
우리가 구해야 할 값은 배열 A가 처음으로 완전히 정렬된 상태가 되기까지 필요한 반복(iteration) 횟수입니다.
예를 들어 입력이 A = [4, 5, 7, 1, 3, 2, 6]이라면 출력은 5가 됩니다. 각 반복 후 배열의 상태가 아래와 같이 변화하기 때문입니다.
- [4, 5, 1, 7, 2, 3, 6]
- [4, 1, 5, 2, 7, 3, 6]
- [1, 4, 2, 5, 3, 7, 6]
- [1, 2, 4, 3, 5, 6, 7]
- [1, 2, 3, 4, 5, 6, 7]
풀이 접근 방식
이 문제는 홀짝 교환 정렬(Odd-Even Transposition Sort) 알고리즘을 그대로 시뮬레이션하는 방식으로 해결할 수 있습니다. 짝수 번째 반복에서는 인덱스 0, 2, 4… 위치에서 인접한 쌍을 비교·교환하고, 홀수 번째 반복에서는 인덱스 1, 3, 5… 위치에서 비교·교환을 수행합니다. 한 바퀴를 돌아도 더 이상 교환이 일어나지 않으면 배열이 정렬된 것이므로 반복을 종료하고, 그때까지의 반복 횟수를 반환하면 됩니다.
구체적인 절차는 다음과 같습니다.
n := size of A
f := 0
Ans := 0
for (Ans = 0;;):
f := 0
for j := 0 to n - 2:
if A[j] > A[j + 1]:
f := 1
if not f:
break
for j := (Ans AND 1) to n - 2 step 2:
if A[j] > A[j + 1]:
swap A[j] and A[j + 1]
Ans := Ans + 1
return Ans핵심 포인트는 다음과 같습니다.
- 매 반복마다 먼저 전체 배열을 훑어 인접한 두 원소 중 큰 값이 앞에 오는 경우가 있는지 확인합니다. 플래그 f가 그대로 0이면 이미 정렬이 끝난 상태이므로 루프를 빠져나갑니다.
- 정렬이 필요하다면 시작 인덱스를 (Ans AND 1), 즉 반복 횟수의 홀짝 여부에 따라 0 또는 1로 번갈아 설정한 뒤, 두 칸씩 건너뛰며 인접한 쌍을 비교·교환합니다.
- 한 번의 패스가 끝나면 반복 횟수 Ans를 1 증가시킵니다.
예제 구현
아래 C++ 코드를 통해 실제 동작을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
int n = A.size();
bool f = 0;
int Ans = 0;
for (Ans = 0;;){
f = 0;
for (int j = 0; j < n - 1; j++)
if (A[j] > A[j + 1])
f = 1;
if (!f)
break;
for (int j = (Ans & 1); j < n - 1; j += 2)
if (A[j] > A[j + 1])
swap(A[j], A[j + 1]);
Ans++;
}
return Ans;
}
int main(){
vector<int> A = { 4, 5, 7, 1, 3, 2, 6 };
cout << solve(A) << endl;
}입력
{ 4, 5, 7, 1, 3, 2, 6 }출력
5
정리
이 알고리즘은 최악의 경우 O(n²)의 시간 복잡도를 가지지만, 각 패스가 독립적인 인접 쌍만을 다루기 때문에 병렬 처리에 적합하다는 특징이 있습니다. 배열이 정렬되었는지 매번 검사한 뒤 홀짝 위치를 번갈아 교환하는 이 단순한 시뮬레이션만으로도, 주어진 순열이 처음으로 정렬되는 데 필요한 정확한 반복 횟수를 손쉽게 구할 수 있습니다.