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

작성일 | In |

Problem : 이중우선순위큐

유형 : 힙

문제 해석

  • 주어진 명령에 맞춰 작업을 수행한 뒤, (최대, 최소) 혹은 (0, 0) 을 리턴하라.

문제 재해석

  • 문자 I 가 들어온 경우 삽입 명령
  • 문자 D가 들어온 경우 삭제 명령
    • 지울게 없는 경우는 무시한다.

해결 전략

  • 가장 큰 값, 가장 작은 값에만 관심을 가진다.
  • 가장 작은 값에도 관심을 가져야 하므로, set을 이용한다.
  • 같은 값이 여러개가 있을 수 있으므로 multiset을 이용한다.

설계, 구현

  • 공백이 있는 문자열이 있으므로, stringstream 을 통해 파싱 한다.

디버깅

  • s.erase(num) 으로 하면 num에 해당하는 것이 전부 지워진다.
  • 반복자를 통해 지워야지 한 개만 지워진다.
    • 이를 위해 끝 부분의 value가 뭔지를 찾고,
    • find를 통해 iterator를 찾은뒤, iterator를 이용해 삭제한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;

multiset<int> ms;

void Parsing(string str) {
    stringstream st(str);

    char cmd;
    int val;
    while (st >> cmd) {
        st >> val;

        if (cmd == 'I') {
            ms.insert(val);
        } else if (cmd == 'D') {
            if (ms.size() == 0) return;

            if (val == 1) {
                int maxValue = *ms.rbegin();
                ms.erase(ms.erase(maxValue));
            } else {
                int _min = *ms.begin();
                ms.erase(ms.begin());
            }
        }
    }
}

vector<int> solution(vector<string> operations) {

    vector<int> answer;
    for (const auto& oper : operations) {
        Parsing(oper);
    }

    if (ms.size() == 0) {
        answer.push_back(0);
        answer.push_back(0);
    } else {
        answer.push_back(*ms.rbegin());
        answer.push_back(*ms.begin());
    }

    return answer;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.TreeMap;

class Solution {
    TreeMap<Integer, Integer> nums = new TreeMap<>();

    public int[] solution(String[] operations) {
        for (String operator : operations) {
            String[] split = operator.split(" ");
            String cmd = split[0];
            int num = Integer.parseInt(split[1]);

            if ("I".equals(cmd)) {
                nums.put(num, nums.getOrDefault(num, 0) + 1);
            } else {
                delete(num);
            }
        }
        int[] answer = new int[2];

        if (!nums.isEmpty()) {
            answer[0] = nums.lastKey();
            answer[1] = nums.firstKey();
        }
        return answer;
    }

    private void delete(final int num) {
        if (nums.isEmpty()) return;

        if (num == -1) {
            int minValue = nums.firstKey();

            nums.put(minValue, nums.get(minValue) - 1);
            if (nums.get(minValue) == 0) nums.remove(minValue);
        } else {
            int maxValue = nums.lastKey();

            nums.put(maxValue, nums.get(maxValue) - 1);
            if (nums.get(maxValue) == 0) nums.remove(maxValue);
        }
    }
}

피드백

  • stringstream 초기화 방법을 까먹었었다.
    • ss.clear() , ss.str(input_str) 잊지말자.
  • multiset 에서 한개만 지우는 법을 몰랐었다.
  • 기존에는 map을 이용했었는데, multiset 사용법을 익히고자 찾아서 공부하였다.