BOJ 11004. K번째 수

🙇‍♀️[Silver V] K번째 수 - 11004

문제 링크

성능 요약

메모리: 51300 KB, 시간: 1196 ms

분류

정렬

제출 일자

2024년 1월 3일 20:30:40

문제 설명

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

입력

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

둘째에는 A₁, A₂, ..., A_N이 주어진다. (-10⁹ ≤ A_i ≤ 10⁹)

출력

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

🚀풀이

데이터 양이 많아서 일반적으로 정렬을하면 시간제한이 걸렸다.

나는 우선순위 큐를 사용해서 문제를 풀었다.

우선순위 큐에서 최소값을 찾는것은 O(logN)의 시간 복잡도를 갖고 있으므로 우선순위 큐에 값들을 다 집어 넣고, k-1번까지는 pop을 해주고 k번째 수를 찾는 방식이다.

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n, k;
priority_queue<int, vector<int>, greater<int>> pq;

void solve()
{
	cin >> n >> k;
	int temp;
	for (int i = 0; i < n; ++i)
	{
		cin >> temp;
		pq.push(temp);
	}

	for (int i = 0; i < k - 1; ++i)
		pq.pop();

	cout << pq.top();
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}