백준 23883 - 선택 정렬3

23883

최종 코드

def selection_sort(N, K, A):
    sortedA = sorted(A)
    numDict = {}

    for i, j in enumerate(A):
        numDict[j] = i

    count = 0
    for i in range(N-1, -1, -1):
        if sortedA[i] != A[i]:
            result = [A[i], sortedA[i]]
            A[i], A[numDict[sortedA[i]]] = A[numDict[sortedA[i]]], A[i]
            numDict[result[0]], numDict[result[1]] = numDict[result[1]], numDict[result[0]]
            count += 1
        if K == count:
            print(*result)
            return
    print(-1)


N, K = map(int, input().split())
A = list(map(int, input().split()))
selection_sort(N, K, A)

핵심 부분 설명

1. 일단 sorted 로 정렬하고 정렬한 배열과 처음 배열을 비교하며 어디를 바꿔야할지 파악함

2. numDict 로 딕셔너리 선언 -> 예: A = [5, 3, 8] 이면 numDict = {5: 0, 3: 1, 8: 2}

   numDict[j] = i 라고 쓰면 {값: 인덱스}
   numDict[i] = j 라고 쓰면 {인덱스: 값}

3. enumerate 로 잘 샤샤샥

def selection_sort(N, K, A):
    sortedA = sorted(A)
    numDict = {}

    for i, j in enumerate(A):
        numDict[j] = i

    count = 0
    for i in range(N-1, -1, -1):
        if sortedA[i] != A[i]:
            result = [A[i], sortedA[i]]
            A[i], A[numDict[sortedA[i]]] = A[numDict[sortedA[i]]], A[i]
            numDict[result[0]], numDict[result[1]] = numDict[result[1]], numDict[result[0]]
            count += 1
        if K == count:
            print(*result)
            return
    print(-1)

4. 일단 result 에 지금 뭐 바꿀지 저장해둠 (두고두고 써먹을 것)

5. 값 교환

6. 딕셔너리도 교환

7. 그 뒤론 알아서 슈슈슉

그렇다면 왜 Dictionary를 사용해야하나?
시간 복잡도를 줄이기 위한 최적의 방법을 찾기 위함
가장 큰 값을 바로 찾기 때문에 O(1)