✅ priority_queue

문제

링크

풀이

1. 문제 접근

메모리 제한이 작은 문제이다.
단순히 N^2개의 수를 배열에 저장할 수 없는 문제이다.

2. 자료구조 선택과 그 이유

따로 정렬을 하지 않아도 되게 우선순위 큐를 사용해보자

3. 문제 해결 로직 (풀이법)

우선순위 큐를 이용해 수를 입력 받을 때마다 큐에 넣어주면 분명 메모리가 초과될 것이다.

N 번째로 큰 수만 구하면 되므로 우선순위 큐의 크기를 N으로 한정하고 오름차순으로 넣어주자.
만약 넣으려는 수가 큐 안에 있는 최대 원소보다 큰데 크기가 N을 넘는다면 가장 큰 원소를 빼고 넣어주면 된다.

의사코드

cin >> N

priority_que<int, vector<int>, greater<int>> pq // 빠지는게 순서가 커지도록 저장
for(i : 1 ~ N){
	for(j : 1 ~ N){
		cin >> num
        if(pq.size < N) pq.push(num)
        else { // 사이즈 초과될 경우
        	if(pq.top < num){
            	pq.pop
                pq.push(num)
            }
        }
	}
}

cout << pq.top

4. 시간 복잡도 분석

O(N^2)

5. 문제에서 중요한 부분

메모리의 한계값을 고려하여 우선순위 큐의 사이즈를 조절하는 것이 중요했다