[Sort]99클럽 코테 스터디 26일차 TIL + 백준/Silver/11004. K번째 수

K번째 수 - 문제 11004

문제 링크

성능 요약

메모리: 623196 KB, 시간: 3732 ms

분류

정렬

제출 일자

2024년 11월 23일 10:48:19

문제 설명

수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.

둘째 줄에는 A1, A2, ..., AN이 주어진다. (-10⁹ ≤ Ai ≤ 10⁹)

출력

A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.

예제 입력 1

5 2
4 1 2 3 5

예제 출력 1

2

 

 

---

 

<내 코드>

import sys

N, K = map(int,(sys.stdin.readline().split()))
A = list(map(int,sys.stdin.readline().split()))
A = A[:N]
A.sort()

sys.stdout.write(str(A[K - 1]))

- 이전에 map을 안써서 번거로웠던게 있었는데, 이제 map을 쉽게 떠올려서 바로 쓸수있게 되어서 좋다

 

- A값을 입력받을 때 원래는 map으로 Int로 변환안했음

그런데 계속 틀렸다고 하는데 map으로 해주니 해결이 되었음

 

 

<모범사례>

대량의 데이터의 경우 QuckSelect알고리즘 사용이 좋음

import sys
import heapq

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

# K번째 수를 찾기 위해 최소 힙을 사용하여 K개의 작은 수를 유지
heapq.heapify(A)
for _ in range(K - 1):
    heapq.heappop(A)
print(heapq.heappop(A))

O(N + K log N)

 

import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
A.sort()
print(A[K - 1])

O(N log N)

 

 

<보충학습>

문자형 정렬 VS 정수형 정렬

- 문자형의 경우 정렬을 하면 유니코드 값을 기준으로 정렬이 됨

(10, 2, 9, 1) -> (1, 10, 2, 9) 순으로 정렬

 

- 정수형의 경우

(10, 2, 9, 1) -> (1, 2, 9, 10) 순으로 정렬