[문제출처 : Codechef] 1부터 N까지의 숫자가 들어있는 리스트가 있습니다. 물론 이 숫자들은 임의의 순서로 배열될 수 있습니다. 우리는 다음과 같은 규칙을 갖는 숫자 배열을 찾으려고 합니다.

1. 임의의 pair (i, j), $1\le i \le j \le N$일 때 $A[i]>A[j]$를 만족하는 pairs의 수
2. $1\le i < N$에 대해서 $A[i] > A[i+1]$을 만족하는 $i$의 수
3. 1번의 수와 2번의 수가 같으면 “YES”를 리턴하고, 아니면 “NO”를 리턴합니다.

여기서 관건은 모든 pair에 대해서 조건을 만족하는지를 찾아보려면 complexity가 $O(N^2)$로 별로 좋지 않다는 것입니다. 그렇다면 어떻게 하면 더 효율적으로 결과를 얻어낼 수 있을까요?

[3, 2, 1]의 경우를 가정해 봅시다. 이 경우 1번은 (3, 1), (3, 2), (2, 1)의 세 가지가 존재하구요, 2번은 (3, 2)와 (2, 1)의 두 가지가 존재합니다. 따라서 이럴 경우 “NO”를 리턴하면 되겠지요? [3, 1, 2]의 경우, 1번은 (3, 1), (3, 2)의 두 가지가 존재하고, 2번은 (3, 1)의 한 가지만 존재하므로 마찬가지로 “NO”입니다. 이런식으로 몇 가지를 하다 보면 결국 다음과 같은 규칙을 발견할 수 있게 됩니다.

$i$를 1에서 N까지 루프 돌면서 만약 index $i$와 $A[i]$의 차이가 2 이상이면 “NO”를 리턴하면 됩니다. 이 경우 complexity는 $O(N)$으로 linear하게 되므로 획기적인 속도의 향상을 얻을 수 있게 됩니다 :)

def isGood(A, N):
    for i, n in enumerate(A):
        if (i+1-n)**2 > 1: #차이가 2 이상이면 "NO"입니다.
            return "NO"
    return "YES"

>>> Ns = [1, 2, 3, 4]
>>> As = [[1], [2, 1], [3, 2, 1], [1, 3, 2, 4]]

>>> for N, A in zip(Ns, As):
...     print isGood(A, N)
YES
YES
NO
YES