[SW Expert Academy] 5205. 퀵 정렬

5205. 퀵 정렬

---

문제)

 

퀵 정렬을 구현해 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번 원소를 출력한다.

 

 

 

 

풀이)

 

def quick_sort(li):
    if len(li) <= 1:
        return li
 
    pivot = li[len(li) // 2]
    sm, eq, mo = [], [], []
 
    for i in li:
        if i < pivot:
            sm.append(i)
        elif i > pivot:
            mo.append(i)
        else:
            eq.append(i)
 
    return quick_sort(sm) + eq + quick_sort(mo)
 
 
 
T = int(input())
for _ in range(T):
    n = int(input())
    li = list(map(int, input().split()))
    print(f"#{_ + 1} {quick_sort(li)[n // 2]}")

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.