📌이중 우선순위 큐
/* 해당 문제 설명은 링크로 대체한다. */
📌풀이
우선순위 큐를 2개 사용한다. 1개는 오름차순으로 정렬되는 큐, 1개는 내림차순으로 정렬되는 큐.
I연산이 일어날 때 숫자를 각 큐에 넣어주고,
D연산이 일어날 때 -1인 경우 오름차순 정렬 큐에서 가장 앞에 원소(최소값)을 빼주고,
1인 경우 내림차순 정렬 큐에서 가장 앞에 원소(최대값)을 빼준다.
주의할 점
I연산이 일어날 때 2개 큐에 값을 넣어주고 삭제 연산은 경우에 따라 1개씩 해준다.
ex. 3번 삽입이 일어나고 2번 D -1, 1번 D 1 일어났다고 가정할 때 오름차순 큐는 2개, 내림차순 큐는 1개 남는다. (균일하게 큐 사이즈를 갖지 못함)
큐 사이즈가 균일할 수 있도록 별도로 cnt 변수를 두어 0이 된 경우에 각 큐를 초기화 시켜줘야 한다.
📌코드
#include <string>
#include <vector>
#include <queue>
#include <sstream>
using namespace std;
vector<int> solution(vector<string> operations)
{
vector<int> answer(2, 0); //2개짜리 배열. 0으로 초기화
priority_queue<int, vector<int>> pq_desc; //내림차순 정렬
priority_queue<int, vector<int>, greater<int>> pq_asc; //오름차순 정렬 (greater 사용 시 구현체 사용 꼭)
int cnt = 0; //q.size();
for (auto oper : operations)
{
if (oper.at(0) == 'I')
{ //삽입 명령 수행
string number = oper.substr(2); //2번 idx부터 끝까지 숫자
pq_desc.push(stoi(number));
pq_asc.push(stoi(number));
cnt++;
}
else
{ //삭제 명령 수행
if (cnt == 0)
continue; //큐가 비었는데 삭제 요청
string number = oper.substr(2); //2번 idx부터 끝까지 숫자
if (number == "1") //최대값 삭제
pq_desc.pop();
else if (number == "-1") //최소값 삭제
pq_asc.pop();
cnt--; //q에서 삭제가 일어났으니
}
//만약 큐가 0이라면 desc, asc 모두 다 지워줌(균일하게 지워주기 위함)
if (cnt == 0)
{
while (!pq_desc.empty())
pq_desc.pop();
while (!pq_asc.empty())
pq_asc.pop();
}
}
if (cnt)
{ //q에 값이 존재한다면
answer[0] = pq_desc.top(); //최대값
answer[1] = pq_asc.top(); //최소값
}
return answer;
}
회고
풀이 중에 set을 이용한 분이 계셨다 ......
나는 이중 우선순위 큐라해서 우선순위 큐를 2개써서 풀어야겠다 라는 생각을 했다.
근데 중복 값 때문에 골치 아파서 결국 큐 사이즈를 삽입 시마다 count 하고, 큐가 0이라면 두 우선순위 큐를 초기화하는 식으로 풀었는데
애초에 set을 이용하면 이 부분은 쉽게 해결할 수 있는 부분이었다 .... 조금만 더 깊게 생각했으면 좋았을텐데 ... 잉 바보
그래도 풀어낸거에 ... 의의를 두고 .. 다음에 다시 풀 때 발전하면 되지 !!
'코딩테스트 공부 > Programmers' 카테고리의 다른 글
[C++] 위클리챌린지 6주차 복서 정렬하기 85002 (0) | 2021.09.06 |
---|---|
[C++] level1 체육복 42862 (0) | 2021.09.01 |
[C++] level2 큰 수 만들기 42883 (0) | 2021.09.01 |
[C++] level2 구명보트 42885 (0) | 2021.09.01 |
[C++] level1 모의고사 42840 (0) | 2021.08.31 |
댓글