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

문제

이중우선순위큐 (https://programmers.co.kr/learn/courses/30/lessons/42628)

풀이

1. 초기 접근

• 문제 조건 해석

  • 입력 문자열의 형태 "I 16", "D 1" -> 문자열 파싱해야한다.

  • 주어지는 operation 길이 n이 1 이상 1000000 미만 -> 최대 O(n log n) 으로 해결해야함.

  • 최소, 최대 값을 뽑아내야 한다. -> 정렬 작업이 필요하다.

• 코드

#include <string>
#include <vector>
#include <set>
#include <sstream>
​
using namespace std;
​
vector<int> solution(vector<string> operations) {
    multiset<int> ms;
    stringstream ss;
    int n = operations.size();
    
    for (int i=0 ; i<n ; i++) {
        char inst;
        int num;
        
        // Parse string into inst and num.
        ss.str(operations[i]);
        ss >> inst;
        ss >> num;
        
        // Clear stringstream.
        ss.clear();
        
        // Distinguish the instruction.
        if (inst == 'I') {
            ms.insert(num);
        } else {
            if (ms.empty())
                continue;
            if (num == 1)
                ms.erase(--ms.end());
            else
                ms.erase(ms.begin());
        }
    }
   
    vector<int> answer;
    if (ms.empty()) {
        answer.push_back(0);
        answer.push_back(0);
    } else {
        cout << *ms.begin() << " " << *ms.end() << endl;
        answer.push_back(*(--ms.end()));
        answer.push_back(*ms.begin());
    }
    
    return answer;
}

• 문자열 파싱

  <sstream> 라이브러리의 stringstream 을 사용한다. 사용법은 다음과 같다.

  #include <sstream>
  ​
  stringstream ss;
  string inst;
  int num;
  ​
  ss.str("I 100");    // Input string into stringstream. 
  ss >> inst;         // inst = "I"
  ss >> num;          // num = 100
  ss.clear();         // Clear stringstream.

  stringstream 을 이용하면, 각 변수 데이터 타입대로 알아서 저장된다. 매우 유용!

• multiset 을 활용하여 최소, 최대값 뽑아내기.

  set 에 말그대로 '집합' 느낌의 자료구조 이고, 중복을 허용하는 집합 자료구조는 앞에 multi를 붙인 multiset 이다.

  매우 좋은게, 삽입 및 삭제의 시간복잡도가 O(n log n) 이라, 시간 복잡도의 부담을 덜 수 있다.

  더 좋은건, 삽입 및 삭제시, 정렬을 유지하며 들어간다는 것이다. 따라서 0번째 인덱스ms.begin()에는 최소 값이, 마지막 인덱스--ms.end()에는 최대값이 저장되어있다. 마지막 인덱스가 ms.end()가 아님을 유의해야 한다.