[백준] 11004번 : K번째 수

유형 : 정렬

[예제]

5 2
4 1 2 3 5

[출력]

2

---

1. 내 풀이

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

_list = list(map(int, sys.stdin.readline().split()))
print(sorted(_list)[K-1])

▷ sys.stdin.readline()을 이용해 소요되는 시간을 줄였다.

▷ sys.stdin.readline()에 대해 참고한 블로그 : [Python 문법] 파이썬 입력 받기(sys.stdin.readline)

▷ 아래 그림을 보면 PyPy3과 Python3에서 실행한 시간을 알 수 있다.

PyPy3 vs Python3

 

 

2. 다른 풀이

출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online

 

** 핵심 아이디어
1. 데이터의 개수는 최대 5,000,000개
- NlogN = 5000000 * 22 = 약 1억
- 시간제한 2초
→ 1초당 5천만 정도의 연산을 간신히 지킬 수 있음

2. 시간 복잡도가 O(NlogN)인 정렬 알고리즘을 이용해야 한다.
3. 고급 정렬 알고리즘(병합/퀵/힙 정렬 등)을 이용해 문제를 풀 수 있다.
4. 또는 파이썬의 기본 정렬 라이브러리를 이용해 해결 가능하다.
5. 시간적 이점을 위해 PyPy3을 선택해 코드를 제출하는 게 좋다.

 

2-1. 병합 정렬 이용

https://leunco.tistory.com/71 → 여기에서 사용된 병합정렬 코드와 거의 동일하다.

[백준] 2751번 : 수 정렬하기 2

 

def merge_sort(array):
    if len(array) <= 1:
    	return array
    
    mid = len(array) // 2
    left= merge_sort(array[:mid])
    right = merge_sort(array[mid:])
    i,j,k = 0,0,0
    
    while i < len(left) and j <len(right): # i와 j가 가리키는 값 비교 -> 작은 값을 k에 넣기
    	if left[i] < right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k += 1
        
    if i == len(left): # 한쪽 리스트가 끝난 경우, 나머지 리스트를 넣어줌
    	while j <len(right):
            array[k] = right[j]
            j += 1
            k += 1
    elif j == len(right):
    	while i < len(left):
            array[k] = left[i]
            i += 1
            k += 1
    return array
    
n,k = map(int, input().split())
array = list(map(int, input().split()))

array = merge_sort(array)

print(array[k-1])

 

2-2. 기본 정렬 라이브러리 이용

n,k = map(int, input().split())
array = list(map(int, input().split()))

array = sorted(array)

print(array[k-1])

 

 

문제 출처 : https://www.acmicpc.net/problem/11004

11004번: K번째 수