[Python] SW Expert Academy - 4843. 특별한 정렬

SW Expert Academy 4843번 특별한 정렬 문제는 N개의 정수가 주어지면 가장 큰 수, 가장 작은 수, 2번째 큰 수, 2번째 작은 수 식으로 큰 수와 작은 수를 번갈아 특별한 정렬을 하여 출력하는 문제이다. 셀렉션, 선택 정렬 알고리즘에 관한 문제로 난이도는 D3다.

 

SW Expert Academy 4843번 특별한 정렬 문제 정보

알고리즘 분류

- 선택 정렬 Selection sort, 셀렉션 알고리즘 Selection Algorithm

난이도

- D3

 

특별한 정렬 문제 요약

• 정수의 개수 N의 범위는 10 이상 100 이하이다.
• 정수의 범위는 1~100이다.
• 주어진 숫자에 대해 특별한 정렬을 한 결과를 10개까지 출력한다.

문제 풀이 과정

1.  선택 정렬, 셀렉션 알고리즘 사용
   • 선택 정렬 과정을 사용하여 k번째로 작거나, k번째로 큰 원소를 찾아주는 셀렉션 알고리즘을 구현한다.
   • N번째로 작은 수, 1번째로 작은 수, N-1번째로 작은 수, 2번째로 작은 수... 순으로 새 리스트에 저장한다.
   • 테스트 케이스 번호, 특별히 정렬된 숫자를 10개까지 출력한다.
2. sort() 사용
   • 입력받은 정수들을 저장한 리스트를 sort()를 사용하여 오름차순으로 정렬한다.
   • N-1번째 원소, 0번째 원소, N-2번째 원소, 1번째 원소... 순으로 새 리스트에 저장한다.
   • 테스트 케이스 번호, 특별히 정렬된 숫자를 10개까지 출력한다.

코드 및 설명

#1 셀렉션 알고리즘 사용: k번째로 작은 원소 찾기
def selection(list, k):
    for i in range(0, k):
        minIndex = i
        for j in range(i+1, len(list)):
            if list[minIndex] > list[j]:
                minIndex = j
        list[i], list[minIndex] = list[minIndex], list[i]
    return list[k-1]

T = int(input())
for tc in range(T):
    N = int(input())
    listA = list(map(int, input().split()))

    sortedListA = []
    for i in range(5):
        sortedListA.extend([str(selection(listA, N-i)), str(selection(listA, i+1))])

    print("#{0} {1}".format(tc+1, ' '.join(sortedListA)))

 

#2 sort() 사용
T = int(input())
for tc in range(T):
    N = int(input())
    listA = list(map(int, input().split()))
    
    listA.sort()

    sortedListA = []
    for i in range(5):
        sortedListA.extend([str(listA[N-(i+1)]), str(listA[i])])

    print("#{0} {1}".format(tc+1, ' '.join(sortedListA)))

---

SW Expert Academy 4843번 특별한 정렬 문제는 셀렉션과 선택 정렬 알고리즘에 관한 문제이며 파이썬을 사용하였다. 난이도가 D3인 것을 보면 선택 정렬을 직접 구현하라고 의도한 문제 같다.