문제출처> 5205. [파이썬 S/W 문제해결 구현] 4일차 - 퀵 정렬🤔
🚩 문제설명
퀵 정렬을 구현해 N개의 정수를 정렬해 리스트 A에 넣고, A[N//2]에 저장된 값을 출력하는 프로그램을 만드시오.
[입력]
첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50
다음 줄부터 테스트 케이스의 별로 정수의 개수 N이 주어지고, 다음 줄에 N개의 정수 ai가 주어진다.
5<=N<=1,000,000, 0 <= ai <= 1,000,000
[출력]
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, , N/2번 원소를 출력한다.
입력
2
5
2 2 1 1 3
10
7 5 4 1 2 10 3 6 9 8
출력
#1 2
#2 6
📝 문제풀이
def partition(left, right):
if left >= right:
return
pivot = left
i = left+1
j = right-1
while i <= j:
while i <= j and A[pivot] >= A[i]: i += 1
while i <= j and A[pivot] <= A[j]: j -= 1
if i <= j:
A[i], A[j] = A[j], A[i]
A[pivot], A[j] = A[j], A[pivot]
partition(left, j)
partition(j+1, right)
T = int(input())
for test_case in range(1, T + 1):
N = int(input())
A = list(map(int, input().split()))
left = 0
right = len(A)
partition(left, right)
print(f'#{test_case} {A[N//2]}')
🔧 해결방법
Hoare-partition 알고리즘을 사용.
1. 분할할 리스트의 맨 0번째 요소를 pivot으로 설정한다.
2. i는 pivot 다음 요소인 1번째 요소 부터 j는 마지막 요소에서 거꾸로 내려가면서 pivot보다 작은 값인지 큰 값인지 비교한다.
i 입장에서 pivot보다 작은 값이면 +1 자리이동을 계속하고 j 입장에서는 pivot보다 큰 값일 경우 -1 자리이동을 계속한다.
i가 지나가는 숫자들은 pivot보다 작은 숫자들만 놓고 j가 지나가는 숫자들은 pivot보다 큰 숫자들만 놓기 위해서.
3. 아직 i <= j 일 경우 i와 j 요소를 서로 바꾸어준다.
만약, i와 j가 이동하던 중, i에서 pivot보다 큰 값, j에서 작은 값이 나타나면 왼쪽은 pivot보다 작은 수들로 이루어진 집합을 만들고 오른쪽은 큰수들로 이루어진 집합을 만들어야 하기 때문에 i와 j는 서로 자리를 바꾸어 준다.
4. 반복문이 다 끝나면 A[pivot], A[j] = A[j], A[pivot] 시행.
pivot이 정렬된 상태일 때 자신이 위치할 곳에 놓임. pivot을 기준으로 왼쪽 집합, 오른쪽 집합 나뉨.
5. left < right 일때까지 partition 함수를 왼쪽 집합, 오른쪽 집합 나눠서 재귀 호출한다. 쪼개서 정렬될때까지 계속.
**이 문제의 포인트
pivot값들 보다 큰 값은 오른쪽, 작은 값들은 왼쪽 집합에 위치시킨다.
집합이 분류되면 pivot의 요소를 두집합의 가운데에 위치시킨다.
피봇이 위치한 곳은 정렬된 상태일 때 자기가 있어야 할 위치에 놓인 것이다.
