[백준] 11004번 : K번째 수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

11004번: K번째 수

 

1. 문제 설명

2. 풀이과정

해당 문제을 퀵 정렬을 구현해 주어진 수를 오름차순으로 정렬하고 K번째 수를 출력하는 방법으로 해결한다면 우선 퀵 정렬에서 가장 중요한 pivot을 정하는 방법을 알아야 한다.

만약 pivot이 K라면 K번째 수를 찾은 것이다.

만약 pivot이 K보다 크다면 pivot의 왼쪽 부분에 K가 있으므로 왼쪽(s ~ pivot - 1)만 정렬을 수행한다.

만약 pivot이 K보다 작다면 pivot의 오른쪽 부분에 K가 있으므로 오른쪽(pivot + 1 ~ e)만 정렬을 수행한다.

 

제일 처음에는 중간 위치를 pivot을 설정하여 제일 앞에 있는 수와 바꾼다.

이후 pivot을 제외한 값에서 각 양 끝의 위치를 i, j로 지정한다.

j을 이동하여 만약 j가 pivot보다 크면 j을 왼쪽으로 이동하는 과정을 반복한다.

j 이동 후, 만약 i가 pivot보다 작으면서 j보다도 작으면 i을 오른쪽으로 이동하는 과정을 반복한다.

pivot을 두 집합을 나눠주는 위치인 i와 j가 만난 위치와 바꿔준다.

 

슈도코드

1. N(숫자의 개수), K(K번째 수) 입력받기
2. A(숫자 데이터 저장 배열) 값 입력받기
3. 퀵 정렬 함수 (시작, 종료, K):
4. pivot = pivot 구하기 함수(시작, 종료)
5. if (pivot == K) : 종료
6. elif (pivot < K) : 퀵 정렬 수행 (pivot + 1, e, K)
7. else : 퀵 정렬 수행 (시작, pivot - 1, K)
8. pivot 구하기 함수 (시작, 종료):
9. 데이터가 2개인 경우에는 바로 비교하여 정렬
10. m(중앙값) 구하기
11. 중앙값을 시작 위치와 swap
12. pivot을 시작 위치 값(A[s])으로 지정
13. i(시작점), j(종료점) 지정
14. while (i <= j):
15. pivot보다 작은 수가 나올 때까지 j 감소
16. pivot보다 큰 수가 나올 때까지 i 증가
17. 찾은 i와 j 데이터 swap
18. pivot 데이터를 나뉜 두 그룹의 경계 index에 저장
19. 경계 index 반환
20. 퀵 정렬 수행
21. K번째 데이터 출력

반응형

3. 소스코드

import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

def quickSort(s, e, K):
    if (s < e):
        pivot = partition(s, e)
        if (pivot == K):
            return
        elif (pivot < K):
            quickSort(pivot + 1, e, K)
        else:
            quickSort(s, pivot - 1, K)

def partition(s, e):
    if (s + 1 == e):
        if (A[s] > A[e]):
            A[s], A[e] = A[e], A[s]
        return e
    
    m = (s + e) // 2
    A[s], A[m] = A[m], A[s]
    pivot = A[s]

    i = s + 1
    j = e
    while (i <= j):
        while (pivot < A[j] and j > 0):
            j -= 1
        while (pivot > A[i] and i < len(A) - 1):
            i += 1
        if (i <= j):
            A[i], A[j] = A[j], A[i]
            i += 1
            j -= 1

    A[s] = A[j]
    A[j] = pivot
    return j

quickSort(0, N - 1, K - 1)
print(A[K - 1])

import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

A.sort()
print(A[K - 1])

하지만 위의 코드처럼 간단하게 작성해도 문제는 동일하게 해결된다.