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

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

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, 3 → 3, 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(*A)
        sys.exit(0)
else:
    print(-1)

💡소요시간 : 10m