프로그래머스 : 이중우선순위큐 - C++

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

---

문제 해석

- 주어진 연산에 맞게 연산 후 결과를 출력 한다.

  I : 숫자를 추가

  D -1 : 최솟값 삭제

  D 1 : 최댓값 삭제

- 연산이 완료 된 후에 남아 있는 최댓값과 최소값을 출력 하면 된다.

---

문제 풀이

- 우선순위 deque 같은게 있으면 좋겠지만 없기 때문에 우선순위 큐로 해결 해야 한다.

- 다만 우선순위 큐는 top() 의 값만 뺄 수 있기 때문에 오름차순, 내림차순의 우선순위큐 2가지를 만들어 사용 한다.

- 이때 내림차순 큐를 만들 수 있지만 수에 -를 붙여 큐에 삽입 하면 top 에 최소값이 들어가게 할 수 있다.

- 오름, 내림차순 큐를 두개 만들고 연산 순서대로 연산 하면 어렵지 않게 닶을 구할 수 있다.

- D -1 이 들어 오면 내림차순큐에서 pop() 을 진행 하고 반대의 경우 오름차순에서 pop() 을 진행 하면 된다.

---

코드

#include <vector>
using namespace std;

int solution(vector<int> a) {
    int answer = 0;
    int len = a.size();
    vector<int> left(len);
    vector<int> right(len);

    int MIN = a[0];
    for (int i = 0; i < len; i++) {
        if (MIN > a[i]) MIN = a[i];
        left[i] = MIN;
    }

    MIN = a[len - 1];
    for (int i = len - 1; i >= 0; i--) {
        if (MIN > a[i]) MIN = a[i];
        right[i] = MIN;
    }

    for (int i = 0; i < len; i++) {
        if (a[i] <= left[i] || a[i] <= right[i]) answer++;
    }
    return answer;
}