문제 소개
[0, 1, ..., N-1]로 구성된 순열(permutation) A가 있다고 가정해 봅시다. 여기서 N은 배열 A의 길이입니다.
전역 역전(global inversion)은 0 <= i < j < N을 만족하는 모든 인덱스 쌍 (i, j) 중에서 A[i] > A[j]인 경우의 수를 의미합니다. 즉, 배열 안에서 더 큰 값이 더 작은 값보다 앞에 있는 모든 경우를 세는 것입니다.
지역 역전(local inversion)은 0 <= i < N을 만족하는 인덱스 i에 대해 A[i] > A[i+1]인 경우의 수입니다. 즉, 서로 인접한 두 원소만 비교합니다.
이 문제는 전역 역전의 개수와 지역 역전의 개수가 정확히 같을 때 true를 반환하면 됩니다. 예를 들어 입력이 [1, 0, 2]라면, 지역 역전은 (1, 0) 한 번뿐이고 전역 역전 역시 (1, 0) 한 번뿐이므로 두 개수가 일치하여 true를 반환합니다.
핵심 아이디어
모든 전역 역전이 동시에 지역 역전이 되려면, 어떤 원소도 자신보다 두 칸 이상 뒤에 있는 원소보다 커서는 안 됩니다. 만약 A[i] > A[j](단, j >= i + 2)인 경우가 존재한다면, 그것은 지역 역전이 아닌 전역 역전이 되어 개수가 어긋나게 됩니다.
따라서 배열을 순회하면서 현재 위치까지 등장한 값들의 최댓값(maxVal)을 추적하고, maxVal이 A[i + 2]보다 커지는 순간이 있다면 false를 반환하면 됩니다. 끝까지 조건을 통과하면 true입니다.
알고리즘 단계
- maxVal을 -1로 초기화하고, n을 배열 A의 크기로 설정합니다.
- i를 0부터 n - 3까지 반복합니다.
- maxVal을 A[i]와 maxVal 중 더 큰 값으로 갱신합니다.
- 만약 maxVal > A[i + 2]라면 false를 반환합니다.
- 반복문이 정상적으로 끝나면 true를 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isIdealPermutation(vector<int>& A) {
int maxVal = -1;
int n = A.size();
for(int i = 0; i < n - 2; i++){
maxVal = max(A[i], maxVal);
if(maxVal > A[i + 2])
return false;
}
return true;
}
};
main(){
vector<int> v = {1,0,2};
Solution ob;
cout << (ob.isIdealPermutation(v));
}입력
[1,0,2]
출력
1
복잡도 분석
배열을 한 번만 순회하므로 시간 복잡도는 O(N)이며, 별도의 추가 공간 없이 상수 변수 몇 개만 사용하므로 공간 복잡도는 O(1)입니다. 이는 역전 쌍을 직접 세는 O(N²) 방식보다 훨씬 효율적입니다.