[백준] 23883번 알고리즘 수업 - 선택 정렬3 ★★★

💡문제접근

• 선택 정렬의 시간복잡도는 O(N^2)
• 배열의 길이 N의 값이 큰 수가 나오면 시간초과를 피할 수가 없다.
• 찾아보니 딕셔너리로 선택 정렬을 구현한 코드가 있어 해당 코드를 참고하고 직접 테스트케이스를 만들어 이해했다.

💡코드(메모리 : 101456KB, 시간 : 1364ms)

import sys
input = sys.stdin.readline

N, K = map(int, input().strip().split())
A = list(map(int, input().strip().split())) # 정렬이 수행되지 않은 리스트
B = sorted(A)       # 정렬이 수행된 리스트
dic = {}            # 사전

for idx, val in enumerate(A):
    dic[val] = idx

cnt = 0
for i in range(N-1, -1, -1):
    # A : [3, 1, 2, 4, 5]
    # B : [1, 2, 3, 4, 5]
    # 2, 3
    if A[i] != B[i]:
        temp = [A[i], B[i]]
        # 2, 0 = 0, 2(인덱싱)
        A[i], A[dic[B[i]]] = A[dic[B[i]]], A[i]
        dic[temp[0]], dic[temp[1]] = dic[temp[1]], dic[temp[0]]
        cnt += 1
    if K == cnt:
        print(*temp)
        sys.exit(0)
else:
    print(-1)

💡소요시간 : 1h 21m