[프로그래머스 Level 3] [힙] 이중우선순위큐 (C++)

안녕하세요! 쏘코입니다.

그동안 일이 있어서 문제를 못풀다가 며칠만에 다시 문제를 풀어봤습니다.

오랜만에 문제를 풀다보니 집중이 잘 안되서 딴짓을 많이 했네요;;

출처 : 프로그래머스 코딩테스트연습 고득점KIT, programmers.co.kr/learn/courses/30/lessons/42628

코딩테스트 연습 - 이중우선순위큐

programmers.co.kr

0. 문제 설명

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어	수신 탑(높이)
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

0.0. 제한사항

operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
operations의 원소는 큐가 수행할 연산을 나타냅니다.
- 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

0.1. 입출력 예

operations	return
[I 16,D 1]	[0,0]
[I 7,I 5,I -5,D -1]	[7,5]

0.2. 입출력 예 설명

16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.
7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.

1. 풀이 과정

최소값과 최대값을 바로바로 확인하기 위해 priority_queue를 2개 만듭니다.(하나는 max-heap, 나머지 하나는 min-heap)

현재 큐에 들어간 값의 수를 나타내는 변수인 cnt를 만듭니다.

필요한건 아니지만 size변수도 만들었습니다.

그리고 이 문제의 핵심 중 하나인 문자열 파싱(여기서는 문자열을 스페이스바로 구분하는 것)을 위해 sstream이라는 방법을 사용했습니다.

문자열 파싱을 위해서 할 수 있는 방법은 2가지가 있는데, C style(char*)인 strtok를 사용하는 방법과 C++ style(string)인 sstream 방법으로 나눌 수 있습니다. 저는 sstream을 사용하는 후자를 선택했습니다.

sstream은 문자열에서 필요한 자료형에 맞는 정보를 꺼낼 때 사용하는 헤더로, stringstream의 준말입니다. 말 그대로 string의 기능과 stream의 기능을 할 수 있죠. string을 보조해 주는 역할을 하는 헤더입니다. 공백과 \n을 제외한 자료형의 정보를 빼냅니다.

먼저 for문을 이용해 operations에 있는 string들에 접근합니다.

그리고 stringstream이라는 속성을 가진 변수를 하나 만들고 temp라는 string변수를 하나 만들어서 operations에 있는 요소들을 공백을 기준으로 구분했습니다.

operations에 있는 요소들의 첫 글자가 I인지, D인지를 구분해서 각각 큐에 넣어주거나 큐에서 최댓값, 최솟값을 빼줬습니다. 넣을 때는 priority_queue를 int형으로 만들었기 때문에, string형태의 숫자를 int형태로 바꾸어서 넣어야 합니다. 그렇기 때문에 형변환을 위해서 stoi()라는 함수를 사용했습니다. 넣은 후에는 cnt를 1 증가시켜줍니다.

뺄 때는 첫 글자가 D여야 하고, '빈 큐에 데이터를 삭제하라는 연산이 주어진 경우 해당 연산을 무시합니다'라는 제한사항을 처리하기 위해 cnt > 0도 만족해야합니다. 두 조건에 모두 만족하면 뒤에 오는 글자가 1이면 최댓값을 빼주고 -1이면 최솟값을 빼줍니다. 그리고 cnt도 1 빼줍니다.

뺀 이후에는 cnt를 확인해야합니다. cnt가 0이면 priority_queue를 비워줘야합니다. 만약 비워주지 않으면 값이 1개 존재하는 상황에서 최솟값이나 최댓값을 빼는 연산이 발생할 경우 빼지 않은 쪽의 priority_queue에 원래는 없어야 할 값이 남아있게 되기 때문에 새로운 원소가 들어오는 경우 원하는 대로 값이 출력되지 않습니다. (실제로 cnt == 0인 경우를 나타낸 조건문을 지우고 채점하면 테스트 1에서 실패합니다.)

이제 answer에 최댓값과 최솟값을 순서대로 넣어줍니다. 만약 priority_queue들에 들어있는 요소가 없으면 0을 2개 넣어주면 끝입니다!

Big-O Notation은 1개의 for문(O(n)), 그리고 for문 안에서 매 턴마다 priority_queue의 push 혹은 pop(O(logn))을 한 번 이상 사용하기 때문에 O(nlogn)입니다.

2. 소스 코드

#include <string>
#include <vector>
#include <queue>
#include <sstream>

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    priority_queue<int, vector<int>, less<int>> pq1; // max-heap
    priority_queue<int, vector<int>, greater<int>> pq2; // min-heap
    int cnt = 0;
    int size = operations.size();
    
    for(int i = 0; i < size; ++i){
        stringstream ss;
        ss.str(operations[i]);
        string temp;
        ss >> temp;
        if (temp == "I"){
            ss >> temp;
            pq1.push(stoi(temp));
            pq2.push(stoi(temp));
            ++cnt;
        }
        else if (temp == "D" && cnt > 0){
            ss >> temp;
            if(temp == "-1"){
                pq2.pop();
            }
            else if(temp == "1"){
                pq1.pop();
            }
            --cnt;
            if (cnt == 0){
                while(!pq1.empty()){
                    pq1.pop();
                }
                while(!pq2.empty()){
                    pq2.pop();
                }
            }
        }
    }
    
    
    if(cnt == 0){
        answer.push_back(0);
        answer.push_back(0);
    }
    else{
        answer.push_back(pq1.top());
        answer.push_back(pq2.top());
    }
    return answer;
}