문제
아이디어
-
처음에는 priority_queue로 풀려고 했는데 생각해보니 priority_queue는 index를 직접 접근을 못하는걸로 알고 있다
-
그래서 앞뒤로 삽입,삭제 가능한 deque를 사용하기로함
-
string 이 값이므로 일단 D인지 I인지를 구문해야함
-
구분한후 뒤에 숫자는 문자이기에 string 헤더를 넣어서 stoi(문자열을 숫자로 바꿔주는 함수) 사용
풀이 순서
- 일단 I가 나오는 경우는 삽입 후 소팅 바로 함 (오름차순)
- D인경우 중 문제에서 보면 비어있는데 삭제 하려는 경우는 무시하라고 함 -> 여기에서 비어있지 않은 경우 연산을 하도록 조건 걸어줌
- 1이면 가장 큰 값 삭제
- -1 이면 가장 작은 값 삭제
- 큐가 비어있는경우 0,0 강제로 넣음
- 큐에 값이 있는 경우 가장 큰 수, 가장 작은 수 순으로 넣음
코드
#include <string>
#include <vector>
#include<queue>
#include<string>
#include<iostream>
#include<cstdio>
#include<functional>
#include<deque>
#include<algorithm>
using namespace std;
vector<int> solution(vector<string> operations) {
vector<int> answer;
deque<int> dq;
for(int i=0;i<operations.size();i++){
string s=operations.at(i);
int num = stoi(s.substr(2, s.length()-2));
if(s[0]=='I'){
dq.push_back(num);
sort(dq.begin(),dq.end());
} else if(!dq.empty()) {
if (num==1){
dq.pop_back();
} else if (num == -1){
dq.pop_front();
}
}
}
if(dq.empty()){
answer.push_back(0);
answer.push_back(0);
} else {
answer.push_back(dq.back());
answer.push_back(dq.front());
}
return answer;
}
정답확인
깃 링크
'Algorithm' 카테고리의 다른 글
[개념] Union-Find 기법 (0) | 2020.10.21 |
---|---|
[프로그래머스] 디스크컨트롤러 - 힙 (0) | 2020.06.24 |
[프로그래머스-그리디] 체육복 (0) | 2020.05.11 |