이중우선순위 큐 C++(힙)[프로그래머스]

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

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

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

 

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

4. 결과

 

---

1. 문제 설명

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

명령어	연산
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

 

문제!!

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

 

제한사항

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

 

예시

opreations	return
["I 16", "D 1"]	[0, 0]
["I 7" , "I 5", "I -5", "D -1"]	[7,5]
["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]	[0, 0]
["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]	[333, -45]

 

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

 

---

2. 문제풀이

이 문제는 효율성 테스트를 하지 않았습니다. 그래서 vector를 이용해서 풀어도 지장이 없습니다. 개인적으로 Lv3보다는 Lv2레벨이 더 적당하다고 생각했던 문제입니다.   이 문제를 풀때 사용하는 값은 최댓값과 최솟값입니다.   문제 또한 이중우선순위 큐니 앞과 뒤에만 사용할 수 있는 deque을 사용하면 된다고 생각했습니다. 그렇지만 deque를 이용해서 구현을 하니 최댓값 혹은 최솟값을 삭제할때마다 정렬을 해야했습니다.   그래서 앞뒤로도 컨트롤이 가능하고 자동으로 정렬이 되는 multiset을 이용했습니다. 두개의 로직은 서로 비슷하지만 중간중간 정렬을 해주냐(deque) 실시간으로 정렬(multiset)을 해주냐의 차이입니다. ※ multiset의 데이터를 접근하기 위해서는 iterator를 이용하셔야 합니다.    end()는 제일끝의 뒤를 반환합니다. 제일 끝의 데이터에 접근하고 싶으시다면 end()에서 한칸 전으로 가야합니다.   풀이는 간단합니다. 들어온 operations을 처음부터 순회합니다. 문자를 기준으로 앞과 뒤를 분리해서 명령을 처리합니다. I라면 뒤에숫자를 set 혹은 deque에 추가합니다. 명령어는 2개이기때문에 I가 아니라면(D라면) 큐가 비어있는지 확인합니다. 큐가 비어있지 않다면 숫자가 1일때 최댓값을 지워줍니다.   만약 multiset을 이용했다면 오름차순 정렬입니다. 제일뒤에가 최댓값입니다. deque를 사용하셨다면 정렬을해서 제일 뒤에값을 제거하면 됩니다. vector를 사용하셨다면 max_element를 사용하시거나 정렬하여 최댓값을 제거하시면 됩니다.   D 뒤에는 1혹은 -1이 오기때문에 1이 아닌경우 처리를 합니다.(-1) multiset을 이용하셨다면 제일 처음이 최솟값입니다. deque를 사용하셨다면 정렬을 해서 제일 앞값을 제거하시면 됩니다. vector를 사용하셨다면 min_element를 사용하시거나 정렬하여 최솟값을 제거하시면 됩니다.   모든 operations연산이 끝났다면 남아있는 데이터를 확인합니다. 데이터가 없다면 {0, 0}을 반환합니다. 데이터가 남아있다면 {최댓값, 최솟값}을 반환하면 됩니다.   아래는 multiset과 deque를 이용한 소스코드입니다.

 

 

---

3. 소스코드

3.1 주석없는 코드

#include <vector>
#include <algorithm>
#include <string>
#include <deque>
#include <set>
 
using namespace std;
 
vector<int> solution(vector<string> operations) {
    multiset<int> mset;
    for (auto o : operations) {
        string a = o.substr(0, 1);
        int num = atoi(o.substr(2).c_str());
        if (a == "I")     mset.insert(num);
        else if (!mset.empty()) {
            if (num == 1)    mset.erase(--mset.end());
            else    mset.erase(mset.begin());
        }
    }
    if (mset.empty())    return { 0 , 0 };
    else    return { *--mset.end() , *mset.begin() };
}
 
vector<int> solution2(vector<string> operations) {
    deque<int> deq;
    for (auto o : operations) {
        string a = o.substr(0, 1);
        int num = atoi(o.substr(2).c_str());
        if (a == "I")     deq.push_back(num);
        else if (!deq.empty()) {
            sort(deq.begin(), deq.end());
            if (num == 1)    deq.pop_back();
            else    deq.pop_front();
        }
    }
    if (deq.empty())    return { 0,0 };
    sort(deq.begin(), deq.end());
    return { deq.back(), deq.front() };
}

3.2 주석있는 코드

#include <vector>
#include <algorithm>
#include <string>
#include <deque>
#include <set>
 
using namespace std;
//set을 이용한 풀이
vector<int> solution(vector<string> operations) {
    multiset<int> mset;
    for (auto o : operations) {
        string a = o.substr(0, 1);//앞의 문자 확인
        int num = atoi(o.substr(2).c_str());//뒤의 숫자 확인
        //앞문자가 I(대문자 i) 라면 데이터 넣기
        if (a == "I")     mset.insert(num);
        //I가 아니고 이 비어있지 않다면 최댓값 혹은 최솟값 제거
        else if (!mset.empty()) {
            if (num == 1)    mset.erase(--mset.end());
            else    mset.erase(mset.begin());
        }
    }
    //멀티셋이 비어있다면 0,0 반환
    if (mset.empty())    return { 0 , 0 };
    //비어있지 않다면 최댓값 최솟값 반환
    else    return { *--mset.end() , *mset.begin() };
}
 
//deque을 이용한 풀이
vector<int> solution2(vector<string> operations) {
    deque<int> deq;//앞으로 데이터 꺼내기용
    for (auto o : operations) {
        string a = o.substr(0, 1);//앞의 문자 확인
        int num = atoi(o.substr(2).c_str());//뒤의 숫자 확인
        //앞문자가 I(대문자 i) 라면 데이터 넣기
        if (a == "I")     deq.push_back(num);
        //I가 아니고 덱이 비어있지 않다면
        else if (!deq.empty()) {
            //정렬 한번하기-> 자동으로 정렬이 안되기때문
            sort(deq.begin(), deq.end());
            if (num == 1)    deq.pop_back();            //오름차순 정렬이므로 뒤에것을 제거
            else    deq.pop_front();        //최소값을 빼야하므로 앞에서 제거
        }
    }
    if (deq.empty())    return { 0,0 };
    //큐가 비어있지 않다면 정렬후 값넣기
    sort(deq.begin(), deq.end());
    return { deq.back(), deq.front() };
}

3.3 테스트 코드 추가

#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <deque>
#include <set>
 
using namespace std;
//set을 이용한 풀이
vector<int> solution(vector<string> operations) {
    multiset<int> mset;
    for (auto o : operations) {
        string a = o.substr(0, 1);//앞의 문자 확인
        int num = atoi(o.substr(2).c_str());//뒤의 숫자 확인
        //앞문자가 I(대문자 i) 라면 데이터 넣기
        if (a == "I")     mset.insert(num);
        //I가 아니고 셋이 비어있지 않다면 최댓값 혹은 최솟값 제거
        else if (!mset.empty()) {
            if (num == 1)    mset.erase(--mset.end());
            else    mset.erase(mset.begin());
        }
    }
    //멀티셋이 비어있다면 0,0 반환
    if (mset.empty())    return { 0 , 0 };
    //비어있지 않다면 최댓값 최솟값 반환
    else    return { *--mset.end() , *mset.begin() };
}
 
//deque을 이용한 풀이
vector<int> solution2(vector<string> operations) {
    deque<int> deq;
    for (auto o : operations) {
        string a = o.substr(0, 1);//앞의 문자 확인
        int num = atoi(o.substr(2).c_str());//뒤의 숫자 확인
        //앞문자가 I(대문자 i) 라면 데이터 넣기
        if (a == "I")     deq.push_back(num);
        //I가 아니고 덱이 비어있지 않다면
        else if (!deq.empty()) {
            //정렬 한번하기-> 자동으로 정렬이 안되기때문
            sort(deq.begin(), deq.end());
            if (num == 1)    deq.pop_back();            //오름차순 정렬이므로 뒤에것을 제거
            else    deq.pop_front();        //최소값을 빼야하므로 앞에서 제거
        }
    }
    if (deq.empty())    return { 0,0 };
    //덱이 비어있지 않다면 정렬후 값넣기
    sort(deq.begin(), deq.end());
    return { deq.back(), deq.front() };
}
 
void print(vector<string> operations, vector<int> answer) {
    vector<int> t = solution(operations);
    if (t == answer)
        cout << "정답" << endl;
    else
        cout << "틀림" << endl;
}
 
int main()
{
    print({ "I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1" }, {0,0});
    print({ "I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333" }, {333, -45});
    return 0;
}

4. 결과