4843. [파이썬 S/W 문제해결 기본] 2일차 - 특별한 정렬 D3

셀렉션 알고리즘

• 저장되어 있는 자료로부터 k번째로 큰 / 작은 원소를 찾는 법
• 최솟값, 최대값 혹은 중간값을 찾는 알고리즘을 의미하기도 함.
• 정렬 알고리즘을 이용하여 자료를 정렬 > 원하는 순서에 있는 원소 가져오기

k번째로 작은 원소를 찾는 알고리즘

• 1번부터 k번째까지 작은 원소들을 찾아 list의 앞쪽으로 이동시키고, list의 k번째를 반환
• k가 비교적 작을 때 유용하며 O(KN)의 수행시간을 필요로 함.

def select(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]

선택 정렬

• 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식
• 셀렉션 알고리즘을 전체 자료에 적용한 것
• 주어진 list 중에서 최솟값을 찾음
• 그 값을 list의 맨 앞에 위치한 값과 교환
• 맨 처음 위치를 제외한 나머지 list를 대상으로 위의 과정을 반복
• 시간 복잡도 : O(N^2)

def selectionSort(a):
	for i in range(0, len(a)-1):
		min = i
		for j in range(i+1, len(a)):
			if a[min] > a[j] :
				min = j
		a[i], a[min] = a[min], a[i]
		

 

4843. [파이썬 S/W 문제해결 기본] 2일차 - 특별한 정렬 D3

보통의 정렬은 오름차순이나 내림차순으로 이루어지지만, 이번에는 특별한 정렬을 하려고 한다.

N개의 정수가 주어지면 가장 큰 수, 가장 작은 수, 2번째 큰 수, 2번째 작은 수 식으로 
큰 수와 작은 수를 번갈아 정렬하는 방법이다.

예를 들어 1부터 10까지 10개의 숫자가 주어지면 다음과 같이 정렬한다.
 
10 1 9 2 8 3 7 4 6 5

주어진 숫자에 대해 특별한 정렬을 한 결과를 10개까지 출력하시오

[입력]
첫 줄에 테스트 케이스 개수 T가 주어진다.  1<=T<=50
다음 줄에 정수의 개수 N이 주어지고 다음 줄에 N개의 정수 ai가 주어진다.
10<=N<=100, 1<=ai<=100

[출력]
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 특별히 정렬된 숫자를 10개까지 출력한다.

현재 문제 접근 방식 생각

1. 큰 수대로 나열
2. 작은 수대로 나열
3. for문을 돌리며 i가 홀수일때는 큰수 배열을 append, 짝수일 때는 작은 수 배열을 append

 
T = int(input())
for test_case in range(1,T+1):
        
    N = int(input())
    ai = list(map(int,input().split()))

    ai.sort() #작은거대로 정렬
    ia = sorted(ai, reverse=True) #큰거대로 정렬
    ans = []
    count = -1
    for i in range(0, len(ai)):
        if len(ans) ==10:
            break
        if i%2==0:    
            count+=1
            ans.append(ia[count]) 
            
        else:
            ans.append(ai[count])
            
    print(f'#{test_case} ' ,end =' ' )       
    for i in ans:
        print(i, end=' ')
print('\\n')

• 여기서의 문제점 : ai.sort()로 ai를 정렬 후, 또 똑같은 리스트를 2번 정렬하고 있음.
• 시간복잡도의 비효율 , so 한번 정렬 후 배열 뒤집기를 이용해 [::-1] 내림차순으로 바꾸는게 좋음

• i가 홀수일때 짝수일때 나눠서 번가락하면서 append하고 있는데, 그냥 한 for문에 같이 둬도됨

정답

T = int(input())
for test_case in range(1, T+1):
    N = int(input())
    nums = list(map(int, input().split()))
    nums.sort()              # 오름차순 정렬
    asc = nums               # 작은 수부터 정렬 배열에 저장
    desc = nums[::-1]        # 큰 수부터 (역순)
    
    # 10개만 출력하면 되므로, 앞의 5쌍 (큰 수, 작은 수)만 사용
    ans = []
    for i in range(5):
        ans.append(str(desc[i])) #어차피 같은 인덱스 번호를 저장해야함 순서대로
        ans.append(str(asc[i]))
        
    # join을 이용해서 한 줄에 정확한 포맷으로 출력
    print(f"#{test_case} {' '.join(ans)}") 

• 배열의 괄호 제거하고 출력하는 것에 당혹감을 느낌;;
• join()은 리스트의 요소들을 하나의 문자열로 합치는 함수임. 공백으로 리스트 요소들을 연결해서 문자열로 변환하겠다는 뜻

근데 문제 유형은 선택 정렬이 아닌가?

• 선택정렬을 이용해서 문제를 풀어보자! sort 이용말고

def selection_sort(arr):
	n = len(arr)
	for i in range(n):
		min_index = i
		for j in range(i+1, n):
			if arr[min_index] > arr[j] :
				min_index = j
		arr[min_index], arr[i] = arr[i], arr[min_index]
	return arr
	

T = int(input())
for test_case in range(1, T+1):
    N = int(input())
    nums = list(map(int, input().split()))
    
    # 선택 정렬을 이용해 오름차순 정렬
    selection_sort(nums)
    
    # 오름차순: 작은 수부터, 내림차순: 큰 수부터
    asc = nums
    desc = nums[::-1]
    
    # 특별 정렬: 큰 수, 작은 수, 2번째 큰 수, 2번째 작은 수 ... 를 10개 출력
    result = []
    for i in range(5):
        result.append(str(desc[i]))
        result.append(str(asc[i]))
        
    # 결과 출력 시 불필요한 공백 없도록 join 사용
    print(f"#{test_case} {' '.join(result)}")