[HackerRank] Lily's Homework .py

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

Lily's Homework | HackerRank

 

def solution(arr):
    cnt = 0
    n = len(arr)
    sorted_arr = sorted(arr)
    index_dict = {arr[i] : i for i in range(n)}
 
    for i in range(n):
        if arr[i] != sorted_arr[i]:
            get_index = index_dict[sorted_arr[i]]
            index_dict[ arr[i] ] = index_dict[ sorted_arr[i]]
            arr[i], arr[get_index] = sorted_arr[i], arr[i]
            cnt += 1

    return cnt

def lilysHomework(arr):
    reversed_arr = list(reversed(arr))

    return min(solution(arr), solution(reversed_arr))

이 문제의 핵심은

# 1. dictionary를 사용하지 않으면 시간초과가난다.

# 2. return min(solution(arr), solution(list(reversed(arr)) 을 해주면 같은 arr을 공유하므로, arr이 2번 정렬되게 된다.

참고