[백준 11004][정렬][파이썬] K번째 수 구하기

문제

https://www.acmicpc.net/problem/11004

11004번: K번째 수

 

---

 

풀이

• 퀵 정렬로 구현하면 시간초과로 통과하지 못한다.
• 병렬정렬로 구현해야 테스트에 통과할 수 있다.

 

퀵 정렬과 병합정렬의 차이점

<표 1.> 퀵 정렬 과 병합 정렬 차이점
참조: https://hongjw1938.tistory.com/192

퀵 정렬과 병합정렬 방식에 대한 깊은 분석을 한 좋은 글이다. 

알고리즘 - Quick(퀵) vs Merge(병합) 정렬(+TCO, 참조 지역성)

 

코드

import sys

input = sys.stdin.readline

# 입력
N, K = map(int,input().split())
arr = list(map(int,input().split()))

def merge_sort(arr):

    if len(arr) <= 1: # 원소가 1개인 경우 종료
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    i,j,k = 0,0,0

    # i, j 가 지칭하는 값 비교, 작은 값을 arr[k] 에 넣기
    while i < len(left) and j < len(right):

        if left[i] < right[j]:
            arr[k] = left[i]
            i += 1

        else:
            arr[k] = right[j]
            j += 1
        
        k += 1

    if i == len(left): # 한쪽 리스트가 끝난 경우 나머지 리스트를 넣어 줌
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1

    elif j == len(right):
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
            
    return arr

arr = merge_sort(arr)

print(arr[K-1])

 

---

 

풀이 (퀵정렬, timeout)

퀵정렬로 구현하면 테스트케이스에 통과하지 못한다.

import sys

input = sys.stdin.readline

# 입력
N, K = map(int,input().split())
arr = list(map(int,input().split()))

def quick_sort(arr, start, end):
    
    if start >= end: # 원소가 1개인 경우 종료
        return

    pivot = start
    left = start + 1
    right = end

    while left <= right:
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and arr[left] <= arr[pivot]:
            left += 1
        
        # 피벗보다 작은 데이터를 찾을때까지 반복
        while right > start and arr[right] >= arr[pivot]:
            right -= 1
        
        # 엇갈린 경우, 작은 데이터와 Pivot을 교체
        if left > right:
            arr[right], arr[pivot] = arr[pivot], arr[right]

    # 분할 중점으로 좌 우, 각각 정렬 수행
    quick_sort(arr, start, right-1)
    quick_sort(arr, right +1, end)

quick_sort(arr, 0, len(arr)-1)
print(arr[K-1])