반응형
안녕하세요. C++을 다루기 위한 기본 적인 자료 구조와 코딩 테스트 등에서 응용될 수 있는 알고리즘을 알아보는 시간을 가지겠습니다.
이번 게시물은 std::priority_queue을 간단히 설명해 보려 합니다.
1) 특징
std::priority_queue는 C++ 표준 라이브러리 컨테이너(C++ STL container) 중 하나로, 우선순위 큐를 구현하는 데 사용됩니다. 해당 자료구조에 삽입된 데이터들은 우선순위에 따라 자동으로 정렬됩닌다. 기본적으로 가장 큰 값이 가장 먼저 pop 되도록 정렬되지만, 우선순위를 변경할 수 있습니다. (다음 게시물에서 우선순위 변경법을 설명 드릴게요!) 또한, 이진 힙(Binary Heap)을 사용하여 구현되어 있기 때문에 삽입과 삭제 연산의 시간 복잡도가 O(log N)으로 효율적입니다.이와같은 std::priority_queue에 대한 attributes와 관련 메서드 사용 예시를 알아보겠습니다.
2) 코딩 테스트 활용 예시
- 최대/최소 K개 요소 찾기
: std::priority_queue를 사용하여 배열을 순회하면서 각 탐색 시점에 가장 크거나 작은 K개의 요소를 std::priority_queue에 저장하고, K개를 넘어가면 우선순위가 가장 낮은 요소를 제거하면서 문제를 해결할 수 있습니다. - 정렬된 배열 병합
: 정렬된 두 개 이상의 배열을 하나의 정렬된 배열로 병합하는 문제입니다. 여러 개의 배열을 std::priority_queue에 저장하고 우선순위에 따라 데이터를 꺼내어 다시 새로운 배열에 저장함으로써 문제를 해결할 수 있습니다. - 중복 문자 제거
: 문자열에서 중복된 문자를 제거하고, 사전 순서로 가장 작은 문자열을 구하는 문제입니다. 문자들을 std::priority_queue에 저장하고, 중복을 제거하면서 가장 작은 문자열을 구할 수 있습니다.
#include <iostream>
#include <string>
#include <unordered_set>
#include <queue>
std::string removeDuplicateLetters(const std::string& s) {
std::unordered_set<char> seen; // 중복 문자 확인을 위한 집합
std::unordered_map<char, int> count; // 문자의 개수를 저장하는 맵
std::priority_queue<char, std::vector<char>, std::greater<char>> pq; // 사전식 순서로 가장 작은 문자를 선택하기 위한 우선순위 큐
// 각 문자의 개수를 세어 맵에 저장
for (char c : s) {
count[c]++;
}
// 문자열을 순회하며 사전식 순서로 가장 작은 문자 선택
for (char c : s) {
count[c]--; // 문자의 개수를 감소
// 이미 선택된 문자면 건너뛰기
if (seen.find(c) != seen.end()) {
continue;
}
// 우선순위 큐에 문자 추가
while (!pq.empty() && pq.top() > c && count[pq.top()] > 0) {
seen.erase(pq.top()); // 우선순위 큐의 top 요소를 집합에서 제거
pq.pop(); // 우선순위 큐의 top 요소 제거
}
pq.push(c); // 문자 추가
seen.insert(c); // 선택된 문자 집합에 추가
}
// 우선순위 큐의 요소들을 순회하며 결과 문자열 생성
std::string result;
while (!pq.empty()) {
result += pq.top();
pq.pop();
}
return result;
}
int main() {
std::string s = "bcabc";
std::string result = removeDuplicateLetters(s);
std::cout << "Original String: " << s << std::endl;
std::cout << "Modified String: " << result << std::endl;
return 0;
}
3) 속성 (Attributes)
std::priority_queue는 <priority_queue> 헤더를 포함해서 사용할 수 있습니다.
우선 다음과 같은 std::priority_queue의 주요 속성과 멤버 함수를 통해 해당 자료 구조를 활용하는 방법을 자세하게 알아보겠습니다.
- push(const T& value)
: 우선순위 큐에 요소를 삽입합니다. - emplace(Args&&... args)
: 우선순위 큐에 요소를 생성하여 삽입합니다. - pop()
: 가장 우선순위가 높은 요소를 제거합니다. - top()
: 가장 우선순위가 높은 요소에 접근합니다. - size()
: 우선순위 큐에 저장된 요소의 개수를 반환합니다. - empty()
: 우선순위 큐가 비어 있는지 여부를 확인합니다. - swap(priority_queue& other)
: 두 우선순위 큐를 서로 교환합니다.
4) 속성 사용 예시
다음은 std::priority_queue의 속성 사용 예시입니다.
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq;
// push(element): 요소 삽입
pq.push(5);
pq.push(2);
pq.push(8);
// top(): 가장 우선순위가 높은 요소에 접근
std::cout << "Top element: " << pq.top() << std::endl;
// pop(): 가장 우선순위가 높은 요소 제거
pq.pop();
// empty(): 우선순위 큐가 비어 있는지 여부 확인
if (pq.empty()) {
std::cout << "Priority queue is empty" << std::endl;
} else {
std::cout << "Priority queue is not empty" << std::endl;
}
// size(): 우선순위 큐에 저장된 요소의 개수 반환
std::cout << "Size of priority queue: " << pq.size() << std::endl;
// swap(): 두 우선순위 큐 교환
std::priority_queue<int> otherPq;
otherPq.push(3);
pq.swap(otherPq);
return 0;
}반응형