알고리즘/문제풀이 - 백준

백준 2075 N번째 큰 수

문제 : https://www.acmicpc.net/problem/2075 서론 메모리 제한이 잡혀있다. 입력값을 전부 배열에 넣거나 큐에 넣으면 메모리초과가 발생할 것이다. 일부만 넣어야 한다. 아이디어 최소힙을 가지는 우선순위 큐를 만든 다음 큐에는 입력값 중 가장 큰 수 n개만 들어가도록 한다. 그럼 큐의 루트 힙이 정답이 될 것이다. 큐의 사이즈가 n개가 될때까지는 그냥 채워주고 n개가 되면 큐의 루트 힙보다 큰 값만 큐에 집어넣고 큐의 루트힙은 빼주면 된다. 그럼 입력값 중 가장 큰 수 n개가 들어있는 큐가 유지된다. 구현 //c++ #pragma warning(disable:4996) #include #include int main() { std::priority_queueq; int n; s..

2019. 8. 22. 11:49