[프로그래머스] 이중우선순위큐

문제 설명

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

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

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

제한사항

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

입출력 예

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

풀이)

vector 로 풀었다.

계속 테스트케이스 1과 6에서 틀리길래 왜그러나 했더니,

sort함수를 최대값과 최솟값 제거하는 곳에 넣어놔서 그랬다.

(마지막 명령문이 제거하라는 명령이 아니라, 숫자를 삽입하라는 명령일 수도 있으므로

 sort함수는 숫자를 삽입한 뒤에 해줘야함을 주의.)

코드)

#include <string>
#include <vector>
#include<algorithm>

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    for(int i=0;i<operations.size();i++){

        if(operations[i][0] == 'I'){
            string tmp ="";
            for(int j=2;j<operations[i].size();j++){
                tmp += operations[i][j];
            }
            answer.push_back(stoi(tmp));
             sort(answer.begin(),answer.end()); //여기서 sort해주기
        }
        else{
            if(answer.empty()) continue;
            if(operations[i][2] == '1'){//최대값삭제
                answer.pop_back();
            }
            else{//최소값 삭제
                answer.erase(answer.begin());
            }
        }

    }
    if(answer.empty()){
        return {0,0};
    }
    else{
        vector <int> temp;
        temp.push_back(answer[answer.size()-1]);
        temp.push_back(answer[0]);
        return temp;
    }
    return answer;
}

+string의 문자열 일부를 반환해주는 함수를 사용하면 더 편리

substr(첫번째 부분문자열 위치, 부분 문자열 길이);

부분 문자열 길이 생략시, 첫번째 문자열 위치부터 ~ 원래 문자열 끝까지 반환.

ex) string tmp = operations[i].substr(2);

+ deque로 푸는 방법이 있다.

deque : vector와 마찬가지로 배열기반 구조 

#include<deque>

deque <int> de;

de[idx]; //인덱스 idx 번째 원소 참조

de.front(); //첫번째 원소

de.begin(); //첫번째 원소 가리킴, iterator와 사용

de.back(); //마지막 원소

de.end(); //마지막원소의 다음을 가리킴, iterator와 사용

de.push_front(), de.push_back(); //삽입함수

de.pop_front(),de.pop_back(); // 제거함수