[스탠다드 반] 우선순위 큐, 순열, n번째 값

우선순위 큐 (priority_queue)

가장 높은 우선순위를 가진 요소가 먼저 나오는 자료구조
삽입, 삭제(pop)은 항상 O(log N) 이고, top()(가장 우선순위 높은 원소 조회)은 O(1)
가장 큰/작은 원소를 순식간에 추출해야 하는 문제에 최적함.

✅ 주요 함수 정리

함수	설명
push(x)	원소 x 삽입 (O(log n))
pop()	가장 높은 우선순위 원소 제거
top()	가장 높은 우선순위 원소 반환 (제거 X)
empty()	큐가 비었는지 확인
size()	원소 개수 확인

최대 힙 예제

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq;

    pq.push(5);
    pq.push(2);
    pq.push(8);

    while (!pq.empty()) {
        cout << pq.top() << " ";  // 가장 큰 값부터 출력
        pq.pop();
    }
}

최소 힙 만들기

priority_queue<int, vector<int>, greater<int>> minHeap;

순열

next_permutation / prev_permutation 사용하기

💠 next_permutation

주어진 범위를 사전순(lexicographical)으로 다음 순열로 바꿔줌

💠prev_permutation

주어진 범위를 사전순으로 이전 순열로 바꿔줌

⚠️ 원본 데이터는 정렬 상태여야 함!!

활용하기 - 조합

주어진 배열이 있을 때 n개의 원소 고르기

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector <int> nums = { 1, 2, 3, 4 };
    vector<int> temp = { 1, 1, 0, 0 };

    do {
        for (int i = 0; i < nums.size(); i++) {
            if (temp[i] == 1)
                cout << nums[i] << ' ';
        }
        cout << endl;
    } while (prev_permutation(temp.begin(), temp.end()));
}
}

n번째 값 찾기

#include <algorithm> 헤더 포함
시작점 부터 n번 째 까지만 정렬!

오름차순

nth_element(v.begin(), v.begin() + n, v.end());

내림차순

nth_element(v.begin(), v.begin() + n, v.end(), greater<>());

문제 풀이

Q1. 배열 {15, 3, 9, 8, 5, 2, 10, 7, 6}에서 짝수만 고려하여 3번째로 큰 수를 출력하세요. (10분)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> nums = { 2, 3, 4 };

    do {
        cout << 1 << " " << nums[0] << " " << nums[1] << endl;
    } while (next_permutation(nums.begin(), nums.end()));
}

Q2. 배열 {1, 2, 3, 4}에서 길이가 3인 순열을 모두 출력하세요. 단, 순열의 첫 번째 원소는 항상 1이어야 합니다.(10분)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector <int> nums = { 1, 2, 3, 4 };

    do {
        for (int i = 0; i < nums.size() - 1; i++) {
            cout << nums[i] << " ";
        }
        cout << endl;
    } while (next_permutation(nums.begin() +1, nums.end()));
}

Q3. 배열 {4, 1, 7, 3, 8, 5}를 5 이상의 값만 내림차순으로 출력하세요. (10분)

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    vector<int> nums = { 4, 1, 7, 3, 8, 5 };
    priority_queue<int> result;

    for (int num : nums) {
        if (num >= 5) {
            result.push(num);
        }
    }

    //큐가 빌 때 까지 반복  
    while (!result.empty()) {
        cout << result.top() << " ";
        result.pop();
    }
}

(출처: 스파르타코딩 내일배움캠프)