AtCoder ABC 135 B – 0 or 1 Swap Python解説

スポンサーリンク

0 or 1 Swap

{1, 2, …, N} を並び替えた数列 p = {p1​, p2​, …, pN} があります。
あなたは一度だけ、整数 pi​  と pj​  を入れ替える操作を行うことができます。操作を行わないことも可能です。
p を昇順にすることができるなら YES を、できないならば NO を出力してください。

AtCoder Beginner Contest 「0 or 1 Swap」

整数 pi​  と pj​  を一度だけ入れ替えて数列pを昇順にできるのか判定する問題ですね。
結論から言ってしまうと、昇順にソートした数列pと元の数列pを比べて、異なる箇所が2箇所以下なら一度の入れ替えで昇順にできます。

n = int(input())
p = list(map(int, input().split()))

cnt = 0

sort_p = sorted(p)

for i in range(len(p)):
    if p[i] != sort_p[i]:
        cnt += 1
        if cnt > 2:
            print("NO")
            break
else:
    print("YES")

先述した通り、上記のコードでは昇順にソートしたsort_pと元の数列pを先頭から順に見ています。数値が異なる箇所があればcnt+1にして、異なる箇所が2箇所を超えたらNOを出力、そうでなければYESを出力しています。