오늘의 알고리즘(백준 11004)

1. 백준 11004, K번째 수 

 

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

11004번: K번째 수

 

---

2. 요구사항 

- 입력값 두개를 받는다. ex) N K

- 입력값 N은 입력 받을 숫자의 개수 

- 입력값 K는 자리 번호이다. 

- N개 만큼의 수를 입력받고 이를 오름차순으로 정렬한다. 

- 그리고 K-1번째 자리에 있는 숫자를 출력한다. index는 0번부터니까 

 

---

3. 어떻게 풀까? 

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

array.sort()

print(array[k-1])

 

 

a) 제출결과 

---

4. 해설 및 정답코드 

- 주어질 수 있는 데이터의 최대 개수가 500만개이다. 

- 데이터의 범위 만큼 자리 번호를 가리키는 K의 범위도 넓다. 

- 그러므로 고급정렬 알고리즘을 사용할 것을 권장한다.

- 이전 포스팅과 동일하게 병합 정렬을 사용하여 해결할 수 있다. 

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):
    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])