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

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

백준 23899 선택 정렬5

☞ 백준 사이트 : https://www.acmicpc.net/problem/23899

 

선택정렬 로직

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] 정렬 완성

▶ 선택정렬의 정의는 이전 글 참고

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

풀이

1. 배열의 끝부분부터 반복한다.
2. 비교리스트와 동일하면 1을 출력한다.
3. 최대값을 찾는다.
4. 최대값과 swap. 만약 해당 위치가 최대값이라면 pass
5. 비교리스트와 동일하면 1을 출력한다.
6. 비교리스트가 없으면 0을 리턴한다.

import sys
#배열 A, B의 크기 N 입력받는다
N = int(sys.stdin.readline())
#배열 A의 원소들을 입력받는다.
A = list(map(int, sys.stdin.readline().rsplit()))
#배열 B의 원소들을 입력받는다.
B = list(map(int, sys.stdin.readline().rsplit()))

def selection_sort(lst, cmpLst):
    lng = len(lst)
    #1.배열의 끝부분부터 반복한다.
    for i in range(lng-1, 0, -1):        
        #2.비교리스트와 동일하면 1을 출력한다.
        if (lst == cmpLst):
            return (print(1))        
        last = i
        #3.최대값을 찾는다.
        for j in range(i-1, -1, -1):
            if (lst[j] > lst[last]):
                last = j        
        #4.최대값과 swap. 만약 해당 위치가 최대값이라면 pass
        if last != i:
            #리스트 값 스왑
            lst[i], lst[last] = lst[last], lst[i]            
            #5.비교리스트와 동일하면 1을 출력한다.
            if (lst == cmpLst):
                return (print(1)) 
    #6.비교리스트가 없으므로 0을 리턴한다.
    return(print(0))
selection_sort(A, B)
"""
5
3 1 2 5 4
2 1 3 4 5
1
"""