문제 링크

https://www.hackerrank.com/challenges/lilys-homework/problem

주의사항

• 이미 정렬된 내용과 그렇지 않은 내용을 구분하여 풀이

  • 이미 정렬된 내용은 그대로 두고
  • 정렬되지 않은 내용만 정렬되어야 하는 위치로 swap

• 오름차순 정렬과 내림차순 정렬 모두 진행한 뒤 swap 횟수의 min값 찾기

  • 동일한 알고리즘을 활용하여 arr, reversed arr에 대입하면
  • 각각 오름차순, 내림차순 정렬 가능

문제 풀이

def checkChangenum(n, arr):
    swap = 0
    idx_dict = {arr[i]:i for i in range(n)}
    sorted_arr = sorted(arr)
    
    for i in range(n):
        if arr[i] != sorted_arr[i]:
            idx_to_go = idx_dict[sorted_arr[i]]
            # idx swap
            idx_dict[arr[i]], idx_dict[sorted_arr[i]] = idx_dict[sorted_arr[i]], idx_dict[arr[i]]
            # value swap
            arr[i], arr[idx_to_go] = arr[idx_to_go], arr[i]
            # swap check
            swap += 1
    return swap

def lilysHomework(n, arr):
    # Write your code here
    reversed_arr = list(reversed(arr))
    
    return min(checkChangenum(n, arr), checkChangenum(n, reversed_arr))