[백준] 23881 파이썬 - 선택 정렬 1

문제

https://www.acmicpc.net/problem/23881

 

풀이

선택정렬 알고리즘을 사용해서 문제를 풀면 된다.

 

선택 정렬이란?

1. 주어진 리스트 값 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 swap 한다.
3. 위 작업을 반복한다.

- 선택 정렬의 시간복잡도 : O(N^2)

- 공간 복잡도: O(1)

 

 

코드

n,k = map(int,input().split())
numbers = list(map(int,input().split()))
cnt = 0

def selection(numbers):
    global cnt
    ans = []
    for i in range(n-1, 0, -1):
        max,index = numbers[0],0

        for j in range(0, i+1):
            if numbers[j] > max:
                max, index = numbers[j], j
        if i != index:
            numbers[i], numbers[index] = numbers[index], numbers[i]
            cnt += 1

            if cnt == k:
                ans.append(numbers[index])
                ans.append(numbers[i])
                return ans

    ans.append(-1)
    return ans

print(*selection(numbers))