[HR] Sort : Lily's Homework

문제요약

• 리스트를 오림차순 또는 내림차순으로 만들기위해 필요한 최소 swap 수 구하기

아이디어

• 리스트를 따로 정렬시켜놓고 앞에서부터 swap하기
• 오름차순, 내림차순을 위한 전체 연산을 두번 해야하는데, 내림차순 정렬을 할 때는 기존 리스트를 뒤집어서 오름차순으로 계산하기
• 중첩 for loop 사용 vs 인덱스를 저장하는 dictionary 활용

결론

• 중첩 for loop, dictionary 모두 정답은 도출할 수 있지만, dictionary가 더 빠르다.

중첩 for loop로 구현한 코드

def sol(arr, l):
    srtd = sorted(arr)
    dic = {}
    cnt = 0 
    dic = {arr[i] : i for i in range(n)}

    for i in range(l):
        if srtd[i] != arr[i]:
            for j in range(l): 
                if srtd[i] == arr[j]:
                    arr[i], arr[j] = arr[j], arr[i]
                    cnt +=1
                    break
    return cnt 

def lilysHomework(arr):
    # Write your code here
    l = len(arr)
    rev = list(reversed(arr)).copy()
    cnt1 = sol(arr, l)
    cnt2 = sol(rev, l)
    return min(cnt1, cnt2)

dictionary로 구현한 코드

def sol(arr, l):
    srtd = sorted(arr)
    dic = {}
    cnt = 0 
    dic = {arr[i] : i for i in range(n)}
        
    for i in range(l):
        if srtd[i] != arr[i]:
            j = dic[srtd[i]]
            dic[arr[i]] = dic[srtd[i]]
            arr[i], arr[j] = srtd[i], arr[i]
            cnt += 1
    return cnt 

def lilysHomework(arr):
    # Write your code here
    l = len(arr)
    rev = list(reversed(arr)).copy()
    cnt1 = sol(arr, l)
    cnt2 = sol(rev, l)
    return min(cnt1, cnt2)