[파이썬] 백준 23881 알고리즘 수업 선택 정렬1

백준 23881 알고리즘 수업 - 선택 정렬 1 문제풀이

백준 23881 선택정렬

선택 정렬이란

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

[3, 1, 2, 5, 4] 선택 정렬 순서

• [3, 1, 2, 5, 4] → 최소값 1, 0번 index와 swap
• [1, 3, 2, 5, 4] → 최소값 2, 1번 index와 swap
• [1, 2, 3, 5, 4] → 최소값 3, 2번 index에 있으므로 pass
• [1, 2, 3, 5, 4] → 최소값 4, 3번 index와 swap
• [1, 2, 3, 4, 5] → 정렬 완성

백준 23881 문제에 있는 선택정렬 의사코드는 최대값에서 거꾸로 찾아가는 코드라서 아래와 같다.

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

[3, 1, 2, 5, 4] 선택 정렬 최대값에서 거꾸로 순서

• [3, 1, 2, 5, 4] 최대값 5, 4번 index와 swap
• [3, 1, 2, 4, 5] 최대값 4, 3번 index에 있으므로 pass
• [3, 1, 2, 4, 5] 최대값 3, 2번 index와 swap
• [2, 1, 3, 4, 5] 최대값 2, 1번 index와 swap
• [1, 2, 3, 4, 5] 정렬 완성

풀이

문제에 있는 알고리즘을 파이썬에 맞게 작성한다.

이때 시간초과가 발생하는데, 정렬 로직을 문제와 같이 함수로 만들어서 호출하면 시간초과 해소된다.

1. 배열의 끝부분부터 반복한다.
2. 최대값을 찾는다.
3. 최대값과 swap. 만약 해당 위치가 최대값이라면 pass
4. 교환 횟수에 도달하면 break

▶ 시간초과 발생 코드

#시간초과 발생 코드
import sys
#배열 A의 크기 N 과 교환횟수 K 를 입력받는다.
N, K = list(map(int, sys.stdin.readline().rsplit()))
#배열 A의 원소들을 입력받는다.
lst = list(map(int, sys.stdin.readline().rsplit()))
cnt = 0
breakYN = False

#1.배열의 끝부분부터 반복한다.
for i in range(N-1, 0, -1):
    last = i
    #2.최대값을 찾는다.
    for j in range(i-1, -1, -1):
        if (lst[j] > lst[last]):
            last = j        
    #3.최대값과 swap. 만약 해당 위치가 최대값이라면 pass
    if last != i:
        #리스트 값 스왑
        lst[i], lst[last] = lst[last], lst[i]
        cnt += 1
    #4.교환횟수에 도달하면 break
    if (cnt == K):
        print(lst[last], lst[i])
        breakYN = True
        break
if breakYN == False:
    print(-1)
"""
5 2
3 1 2 5 4
2 3
"""

 

▶  선택 정렬 로직을 함수로 재구성

import sys
#배열 A의 크기 N 과 교환횟수 K 를 입력받는다.
N, K = list(map(int, sys.stdin.readline().rsplit()))
#배열 A의 원소들을 입력받는다.
lst = list(map(int, sys.stdin.readline().rsplit()))
#선택정렬 함수
def selection_sort(N):
    cnt = 0    
    #1.배열의 끝부분부터 반복한다.
    for i in range(N-1, 0, -1):
        last = i
        #2.최대값을 찾는다.
        for j in range(i-1, -1, -1):
            if (lst[j] > lst[last]):
                last = j        
        #3.최대값과 swap. 만약 해당 위치가 최대값이라면 pass
        if last != i:
            #리스트 값 스왑
            lst[i], lst[last] = lst[last], lst[i]
            cnt += 1
        #4.교환횟수에 도달하면 break
        if (cnt == K):            
            return (print(lst[last], lst[i]))
    return(print(-1))
#선택정렬 함수 호출
selection_sort(N)
"""
5 2
3 1 2 5 4
2 3
"""