알고리즘 스터디 - HackerRank : Lily's Homework

문제 해석

• 조지가 릴리에게 언제든지 놀러나가자고 하지만 릴리는 숙제를 핑계로 틩기고 있다. 조지는 빨리 릴리가 숙제를 끝내서 자기랑 놀게 만들고 싶게 만들고 싶어한다.
• arr 배열내 a[0], a[1], ..., a[n-1]로 총 n개가 존재를 하는데 조지는 2개의 배열 위치를 바꿔가면서 배열 앞뒤의 값의 차이가 최소가 될 수 있도록 하려고 한다.
• 예를 들어, arr = [7, 15, 12, 3]이 있으면 3과 7을 바꾸고, 7과 15를 바꿔 최종적으로 [3, 7, 12, 15]를 만드는 것이다.

어떤 알고리즘을 사용해야할까?

• 이미 정렬된 것과 정렬되지 않은 것을 비교해서 진행해보자.
• n이 1 <= n <= 10^5라서 시간 복잡도 최대가 5*log(5)이다.
• 그렇다면 배열을 입력받을 때 가장 작은 것과 큰 것 그리고 순서대로 정렬을 할 때 어떤 방식을 사용하는 것이 좋을까?

직접 논리구조를 짜보자

처음 받은 값을 기준으로 그 다음으로 작은 값의 위치를 찾는다. 
2 5 3 1 이면
2 | 5 3 1 중 가장 작은 것 -> 1 5 3 2
5 | 3 2 중 가장 작은 것 -> 1 2 3 5

2 4 5 3 1 일 때는 어떻게 할까?
2에서 4로 갈 때는 오름차순으로 할 바꿀 필요가 없다. 그러면 나머지 5 3 1 중 가장 작은 것을 4와 바꾼다.
2 4 | 5 3 1 -> 2 1 5 3 4
2 | 1 5 3 4 -> 1 2 5 3 4
1 2 5 | 3 4 -> 1 2 3 5 4
1 2 3 5 | 4 -> 1 2 3 4 5
이때 list.index()을 사용하게 되면 시간복잡도가 O(n)으로 O(n-1!)가 시간 복잡도로 너무 오래 걸리게 된다.
따라서 딕셔너리로 조회를 하면서 해야한다.
새로운 딕셔너리 생성한다.
각 값마다 위치를 키-값 형식으로 저장해 놓는다. 
형식은 키 : a[i], 값 : i
딕셔너리에서 조회는 O(1) 밖에 걸리지 않기 때문에 짧은 시간 내에 스왑 횟수를 구할 수 있다. 

알고리즘 코드

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'lilysHomework' function below.
#
# The function is expected to return an INTEGER.
# The function accepts INTEGER_ARRAY arr as parameter.
#

def lilysHomework(arr):
    # Write your code here
    sort_array = sorted(arr)
    rev_array = list(reversed(arr))

    dict_array = {sort_array[i]: i for i in range(n)}

    swap_count = 0
    i = 0
    while i < n:
        if sort_array[i] == arr[i]:
            i += 1
            continue
        swap_count += 1
        arr[dict_array[arr[i]]], arr[i] = arr[i], arr[dict_array[arr[i]]]
        dict_array[sort_array[i]] += 1

    dict_array_2 = {sort_array[i]: i for i in range(n)}

    swaps_rev = 0
    i = 0
    while i < n:
        if sort_array[i] == rev_array[i]:
            i += 1
            continue
        swaps_rev += 1
        rev_array[dict_array_2[rev_array[i]]], rev_array[i] = rev_array[i], rev_array[dict_array_2[rev_array[i]]]
        dict_array_2[sort_array[i]] += 1
    
    return min(swap_count, swaps_rev)

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input().strip())

    arr = list(map(int, input().rstrip().split()))

    result = lilysHomework(arr)

    fptr.write(str(result) + '\n')

    fptr.close()