[HackerRank] Almost Sorted

문제

https://www.hackerrank.com/challenges/almost-sorted/problem

접근 방식

정렬된 배열과 원래 배열을 비교하여 다른 경우, 해당 인덱스들을 저장하여 조건을 만족하는지 확인했다.

코드

# 뒤집어서 비교하기
def valid_when_reversed(idxes, arr1, arr2):
    return tuple(arr1[idxes[-1]:idxes[0]:-1]) == tuple(arr2[idxes[0]:idxes[-1]])


def almostSorted(arr):
    sarr = sorted(arr)

    idx = 0
    idxes = []
    for x1, x2 in zip(arr, sarr):
        if x1 != x2:
            idxes.append(idx)
        idx += 1

    if not idxes:  # 완전 sorted
        print("yes")
    elif len(idxes) == 2 and arr[idxes[0]] == sarr[idxes[1]] and arr[idxes[1]] == sarr[idxes[0]]:  # swap 가능
        print("yes")
        print(f'swap {idxes[0] + 1} {idxes[1] + 1}')
    elif valid_when_reversed(idxes, arr, sarr):  # reverse 가능
        print("yes")
        print(f'reverse {idxes[0] + 1} {idxes[-1] + 1}')
    else:  # 규칙대로 정렬 불가
        print("no")

처음 TC 5개 정도 틀렸는데, 세번째 조건(reverse 비교)할 때 연속된 인덱스들의 집합인지(조건1) && 뒤집을 수 있는지(조건2) 알아봐서였다. 생각해보니 연속되지 않은 경우가 있을 거 같아(정렬 전, 정렬 후 같은 위치, 그러나 정렬되어야 할 부분 배열의 일부) 연속된 인덱스들인지 비교하는 함수를 아예 뺐다.