알고리즘 수업 - 선택 정렬 1

알고리즘 수업 - 선택 정렬 1

23881번: 알고리즘 수업 - 선택 정렬 1

---

문제 정의

selection_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다.
    for last <- N downto 2 {
        A[1..last]중 가장 큰 수 A[i]를 찾는다
        if (last != i) then A[last] <-> A[i]  # last와 i가 서로 다르면 A[last]와 A[i]를 교환
    }
}

입력

첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 10,000), 교환 횟수 K(1 ≤ K ≤ N)가 주어진다.

다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

출력

K 번째 교환되는 두 개의 수를 작은 수부터 한 줄에 출력한다. 교환 횟수가 K 보다 작으면 -1을 출력한다.

---

개인적인 해석

 

---

개인적인 풀이

 

import sys
from collections import defaultdict

def selection_sort(A, N, exchange_cnt = 0):
    exchange = defaultdict()
    tmp_A = A
    for i in range(N-1, 0, -1):
        max_val = max(tmp_A)
        max_idx = tmp_A.index(max_val)
        chk_val = tmp_A[i]
        chk_idx = i
        if max_val != chk_val:
            exchange_cnt += 1
            exchange[exchange_cnt] = [chk_val, max_val]
            A[max_idx] = chk_val
            A[chk_idx] = max_val
        tmp_A = A[:i]
    return A, exchange

input = sys.stdin.readline().rstrip().split(" ")
N = int(input[0])
K = int(input[1])
A = list(map(int, sys.stdin.readline().rstrip().split(" ")))

A_new, exchange = selection_sort(A, N)

try:
    o = exchange[K]
    o.sort()
    print(" ".join(list(map(str,o))))
except KeyError:
    print(-1)

---