프로그래머스 - 이중우선순위큐(Level 3)/Wanna Be 컴잘알

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42628

코딩테스트 연습 - 이중우선순위큐 | 프로그래머스

-문제-

 

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

 

명령어수신	탑(높이)
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]

 

입출력 예 설명

 

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

 

-접근-

1. 삭제도 최대값, 최소값이 삭제되고 return해야할 값이 큐에 들어있는 최대값과 최소값과 최소값이 되므로 큐라는 자료구조의 특성에 국한될 필요가 없다.

따라서 벡터를 사용하여 sort를 매번 해줘서 오름차순을 유지시켜준다.

 

-코드-

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

// 1. 이중 우선순위 큐 설명
// 2. I 숫자: 큐에 주어진 숫자를 삽입한다.
// 3. 큐에서 최대값을 삭제.
// 4. 큐에서 최솟값을 삭제한다.

int max_value = -0x7FFFFFFF;
int minimum_value = 0x7FFFFFFF;


int search_index(int value, vector <int> v) {
	int number=0;

	for (int i = 0; i < v.size();i++) {
		if (v[i] == value) {
			number = i;
			break;
		}
	}

	return number;
}

vector<int> solution(vector<string> operations) {
	vector<int> v;
	vector <int> answer;

	for (auto i : operations) {
		if (i[0] == 'I') { //삽입
			string  num = i.substr(2, i.length()-1);
			int number = atoi(num.c_str());
			v.push_back(number);
			sort(v.begin(), v.end());
		}
		else { //삭제
			if (v.size() == 0)
				continue;

			max_value = v[v.size() - 1];
			minimum_value = v[0];

			if (i[2] == '1') {//최대값 삭제
				int which_index = search_index(max_value, v);
		
				v.erase(v.begin() + which_index, v.begin() + which_index+1);
		
				
			}
			else {//최소값 삭제
				
				int which_index = search_index(minimum_value, v);
				v.erase(v.begin() + which_index, v.begin() + which_index + 1);
				
			}
		}
	}

	if (v.size() == 0) {
		answer.push_back(0);
		answer.push_back(0);
	}
	else {
		answer.push_back(v[v.size() - 1]);
		answer.push_back(v[0]);
	}

	return answer;
}