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

jh Seo·2023년 7월 5일

프로그래머스

목록 보기

16/32

개요

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

명령어 수신 탑(높이)
I 숫자 큐에 주어진 숫자를 삽입합니다.
D 1 큐에서 최댓값을 삭제합니다.
D -1 큐에서 최솟값을 삭제합니다.
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

접근 방식

최대값과 최솟값을 가지고 다루는 형식이라
우선순위큐를 두개 사용해서 푸는 방식으로 접근했다.
하지만 우선순위큐를 두 개 사용해서 풀려니 제약이 많았다.
생각한 방식은 set을 이용해 이미 빠진 값들을 저장하는 것이다.
두 큐에서 매 pop 연산마다 현재 top값이 다른 큐에서 이미 빠진 값인지
set에서 find연산을 통해 체크해야 한다.
하지만 최대값이 여러개있을때는 그 중 하나만 빼야한다고 조건에 있으므로
set을 그냥 int값만 저장하는 방식이아니라 pair형태로 값과 해당 값의 operation에서 인덱스값까지 저장해서 풀어야한다.
이렇게 구현하면 생각할 조건이 많아보여서 더 최적화할 수 있는 방식을
생각하던 중 multiset이 떠올랐다.
중복값을 허용하는 set으로 top값만 접근할 수 있는 우선순위큐와는 다르게 iterator을 통해 첫값 끝값 접근할 수 있어서 편리하다.

구현 방식은 각 operation의 string값을 순회하며
해당 string의 첫 원소값이 I일때와 D일때 나눠서 생각했다.

I일 때는 숫자에 해당하는 char부분을 숫자로 변환하여
저장하였고,

case 'I':
	inputNum=0;
   for(int i=2;i<elem.length();i++){
   	if(elem[i]=='-') continue;
       inputNum=inputNum*10+ (elem[i] -'0');
	}
   if(elem[2]=='-'){
   	inputNum *= -1;
	}
   mulSet.insert(inputNum);

   break;

D일때는 -포함인지 아닌지를 string.find함수로 찾은 뒤,
-일때는 begin값 지워주고, -없을때는 end()전 값 지워줬다.

case 'D':
	if(mulSet.empty()) break;
	if(elem.find("-") != string::npos){
		mulSet.erase(mulSet.begin());
	}
	else{
   		iter=mulSet.end();
		mulSet.erase(--iter);
	}
   break;

전체 코드

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    multiset<int> mulSet; 
    multiset<int>::iterator iter;
    int inputNum=0;
    for(string elem : operations){
        switch(elem[0])
        {
            case 'I':
                inputNum=0;
                for(int i=2;i<elem.length();i++){
                    if(elem[i]=='-') {
                        continue;
                    }
                    inputNum=inputNum*10+ (elem[i] -'0');
                }
                if(elem[2]=='-'){
                     inputNum *= -1;
                }
                mulSet.insert(inputNum);

                break;
            case 'D':
                if(mulSet.empty()) break;
                if(elem.find("-") != string::npos){
                    mulSet.erase(mulSet.begin());
                }
                else{
                    iter=mulSet.end();
                    mulSet.erase(--iter);
                }
                break;
        }
    }
    if(mulSet.empty()) {
        answer.push_back(0);
        answer.push_back(0);
    }
    else{
        iter=mulSet.end();
        answer.push_back(*(--iter));
        answer.push_back(*(mulSet.begin()));
    }
    
    return answer;
}

문풀후생

많은 실수가 있던 문제였다.
우선 case I: 에서

if(elem[i]=='-') {
	continue;
}

이 부분을 아무 생각없이

if(elem[2]=='-') {
	continue;
}

이렇게 구현했더니 elem[2]가 -인 상황이면 전부 continue가 되어서
음수값은 전부 continue당했다..

또한 char형을 숫자로 바꿔주는

inputNum=inputNum*10+ (elem[i] -'0');

이부분도 '0'을 빼야 숫자가 나오는데
빼먹고 그냥 elem[i]를 더했다가 너무 큰수가 나워서 애먹었었다.

이건 지금 생각해보면 실수라기보단 char형의 특성을 정확히 인지하지 못해서 생긴 상황같다.

확실히 char형을 int형으로 형변환하면 해당하는 문자의
아스키코드 숫자가 나오는 부분을 이해하고 넘어가야겠다.

또한 지금은

iter=mulSet.end();
mulSet.erase(--iter);

이런식으로 구현했지만

mulSet.erase(--mulSet.end());

이렇게 구현해도된다.

jh Seo

코딩 창고!

이전 포스트

[프로그래머스] 디스크 컨트롤러

다음 포스트

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