수열 정렬

1015번: 수열 정렬

 

나의 코드

from itertools import permutations
import sys

def _su_sort(n, array_a):
    answer = []
    n_array = [str(i) for i in range(n)]
    for p_array in permutations(n_array, n):
        b_array = [-1] * n
        for i in range(n):
            b_array[int(p_array[i])] = array_a[i]
        if (b_array == sorted(b_array)):
            answer.append(p_array)
    return ' '.join(sorted(answer)[0])

n = int(sys.stdin.readline())
array_a = sys.stdin.readline().rstrip().split()
print(_su_sort(n, array_a))
>>> 시간 복잡도 : O(n! * n)

 

수정 코드

import sys

def _su_sort(n, array_a):
    answer = []
    sort_array_a = sorted(array_a)
    for i in range(n):
        answer.append(sort_array_a.index(array_a[i]))
        sort_array_a[sort_array_a.index(array_a[i])] = '-1'
    print(*answer)

n = int(sys.stdin.readline())
array_a = list(map(int,sys.stdin.readline().rstrip().split()))
_su_sort(n, array_a)

 

시간 복잡도

for i in range(n) :  배열길이 만큼 순회 ( 선형 시간 복잡도 )
    sort_array_a.index(array_a[i]) : 특정 값의 인덱스 정보 가져오기 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n**2) )