[LeetCode] 775. Global and Local Inversions

문제

[0, n-1] 순열에서 global inversion 수와 local inversion 수가 같은지 판정.

• global: i < j이고 nums[i] > nums[j]인 모든 쌍
• local: 바로 옆끼리 뒤집힌 쌍 (nums[i] > nums[i+1])

첫 시도의 문제

이중 루프로 global을 직접 세면 O(n²). n ≤ 10⁵라 TLE 발생함. 로직은 맞았지만 복잡도가 잘못됨.

핵심 관찰

local은 전부 global에 포함되므로 항상 global ≥ local임.

따라서 둘이 같다는 건 거리 2 이상 떨어진 inversion이 하나도 없다는 뜻. 개수를 세는 문제가 아니라 존재 판정 문제로 바뀜.

풀이 1: 순열 조건 활용 — O(n)

순열이므로 값 v의 제자리는 인덱스 v임.

어떤 값이 제자리에서 2칸 이상 벗어나면 거리 2 이상 inversion이 반드시 생김. 예: 3이 인덱스 1에 있으면 3보다 작은 값(0,1,2) 셋 중 최소 둘이 뒤에 깔리고, 그중 하나는 거리 2 이상이 됨.

반대로 모든 값이 1칸 이내면 가능한 형태는 이웃 스왑뿐이고, 이웃 스왑은 local inversion만 만듦.

function isIdealPermutation(nums: number[]): boolean {
    return nums.every((v, i) => Math.abs(v - i) <= 1);
}

풀이 2: 순열 조건 없이 — O(n)

nums[i] 기준으로 2칸 이상 앞의 최댓값이 자기보다 크면 거리 2 이상 inversion 존재함.

i-1은 거리 1(local)이라 일부러 max에서 제외함.

function isIdealPermutation(nums: number[]): boolean {
    let prefixMax = -Infinity; // nums[0..i-2]의 최댓값
    for (let i = 2; i < nums.length; i++) {
        prefixMax = Math.max(prefixMax, nums[i - 2]);
        if (prefixMax > nums[i]) return false;
    }
    return true;
}

예: [1,2,0] → i=2에서 prefixMax=1 > 0 → false. [1,0,2] → 1 > 2 아님 → true.

중복·음수가 있어도 동작함. 순열 조건은 이를 |nums[i] - i| ≤ 1로 줄여주는 보너스였음.

정리

global == local
⟺ 거리 2 이상 inversion 없음
⟺ 모든 값이 제자리에서 1칸 이내 (순열일 때)