[Baekjoon] #23881 알고리즘 수업 - 선택 정렬1
📝 문제
https://www.acmicpc.net/problem/23881
💡 풀이 방법
💬 아이디어
문제의 제목에서도 확인할 수 있듯이 선택 정렬의 개념을 응용하여 해답을 구하는 문제이다.
교환이 발생하는 과정을 확인해야 하기 때문에 교환 횟수를 체크할 변수 cnt
를 선언하고, 최종적으로 출력될 값 answer
를 선언한다.
루프를 진행하면서 원소의 자리 교체가 이루어지는 경우 cnt + 1
을 하여 cnt
와 교환 횟수 K
가 같아지는 시점에 answer
의 값을 변경한다.
💬 알고리즘
- 배열 A의 크기
N
, 교환 횟수K
, 배열 A의 원소를 각각sys.stdin.readline()
을 활용하여 입력받는다. - 배열 A의 원소 중 가장 큰 값을
max_item
변수에 저장한다. max_item
이 가장 마지막 원소가 아닐 경우, 마지막 원소와 자리를 교환한 뒤cnt
에 1을 더해준다.- 정렬된 값을 제외한 배열에서 위의 과정을 반복한다.
cnt
의 값이K
가 되었을 때,answer
의 값을arr[i]
,max_item
으로 포매팅한다.
💻 소스코드
import sys
n, k = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
cnt = 0
answer = -1
def selection(arr):
global cnt, answer
for i in range(n-1, 0, -1):
max_item, idx = arr[0], 0
for j in range(1, i+1):
if arr[j] > max_item:
max_item, idx = arr[j], j
if arr[i] != arr[idx]:
arr[i], arr[idx] = arr[idx], arr[i]
cnt += 1
if cnt == k:
answer = f'{arr[idx]} {arr[i]}'
return answer
print(selection(arr))
Author And Source
이 문제에 관하여([Baekjoon] #23881 알고리즘 수업 - 선택 정렬1), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@seongmini/Baekjoon-23881-알고리즘-수업-선택-정렬1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)