문제
https://programmers.co.kr/learn/courses/30/lessons/42628
풀이
처음에는 우선순위 큐를 통해서 pair로 구간힙을 만들어서 풀려는 시도를 하였는데. 반개만 들어가 있는 pair에 대한 처리를 불가능하다고 생각해서 그만두었다. (구간힙에 대한 STL이 있는지 찾아봤지만 없어서 포기..) 또한 삽입할때도 반개짜리를 새로 만들어서 삽입할지, 있는 반개짜리에 넣어서 완전한 pair를 만들지에 대한 논의가 필요하다. 다만 이건 STL을 사용하지 않고 구현으로 한다면 구간힙으로 접근하는게 합리적일 것 같다. (시간을 모르겠지만 완성도 측면에서는..?)
그 후에 어떻게 풀지에 대해서 몇시간 동안 고민했는데, 힙(우선순위큐)을 두개를 사용한 방법으로 접근하였다. 원래 이렇게 시도하려고 했는데 관련된 방법이 떠오르지 않아서 오래걸렸다.
일단 두개로 구현하다면 최소 힙과, 최대 힙을 한개씩 만드는 것이 이상적인데 만약 어떻게든 최소든 최대든 판단해서 두개 중 하나에 넣는다고 가정하면, 생각해보면 알겠지만 아무리 잘 넣어서 두 힙의 개수가 같더라도 한쪽만 계속 빼다보면 최소나 최대 힙이 0개가 되는 상황이 발생하고, 그때는 최대나 최소 힙 (순서주의)의 리프노드를 접근해야 하는 상황이 발생하는데 이렇게 하면 최소나 최대 둘중 하나는 처리하는데 O(n)인 상황이 발생한다. (원래는 O(log n)) 따라서 둘다 O(log n)으로 처리하려면 다른 방법을 사용해야 한다.
그다음 직관적으로 떠올릴 수 있는 방법이 그냥 하나의 값을 두 힙에 모두 넣어버리는 방법인데 이 경우 한 힙에서 뺏다면 다른 힙에는 값이 남아있는 기이한 상황이 발생한다. 따라서 힙이라는 특성을 이용해 중복을 처리하는 방법을 고안하면 아래와 같다.
- 최소 힙의 최소값이 최대 힙의 최대 값보다 크면 둘 중 하나는 허수 (이미 빠져나간 수)이다.
- 숫자의 개수를 따로 관리해서 넣은 숫자의 개수가 0인데 (다 뺀경우) 힙에 숫자가 남아있으면 허수이다.
라고 생각할 수 있다. 관련된 증명은 적진 않겠다. (몰라서) 다만 2를 먼저 구현하고 1을 구현하려고 했는데 2만으로 프로그래머스에는 정답으로 처리되었다. 아마 문제가 발생하는 경우가 모두 2번에 해당이 되어서 알아서 오류 처리가 된 것 같다. (아니면 프로그래머스 TC가 적어서 운좋게 통과 되었을 가능성이 있다. 이는 확인을 해봐야 한다. 프로그래머스 효율성 테스트와 TC 개수가 빡빡하지 않아서 제대로된 확인을 해봐야된다.)
실수
-
저번과 마찬가지로 관련 STL 사용이 미숙해서 인터넷에 검색해서 했다. 때문에 많은 시간이 들었던 것 같다. STL 연습을 해야한다.
-
이중우선순위큐를 구현하는데 생각만 2~3시간 이상 걸린 것 같다. 만약 1개를 넣어서 해결하는게 불가능하다면 2개를 넣는 것을 바로 생각하면 되었는데 이걸 생각하는데 오래 걸리는게 문제였던건 같다. 다음부터는 문제를 쉽게 생각하고 쉽게 접근하려고 해야겠다.
코드
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <sstream>
#define max_pop 1
#define min_pop 2
#define input 3
#define blank 4
using namespace std;
bool compare(int& front, int& back){ // min heap을 위한 compare 함수
return front < back;
}
priority_queue<int> max_pq;
priority_queue<int, vector<int>, greater<int>> min_pq;
int depq_size = 0;
void depq(int type, int num){ // 이중우선순위큐 구현
if(type == max_pop){
if(depq_size == 0){
return;
}
max_pq.pop();
depq_size--;
}
else if(type == min_pop){
if(depq_size == 0){
return;
}
min_pq.pop();
depq_size--;
}
else if(type == input){
max_pq.push(num);
min_pq.push(num);
depq_size++;
}
if(depq_size == 0){ // size가 0이면 기존에 있는 값 모두 없애줌
while(max_pq.size() != 0){
max_pq.pop();
}
while(min_pq.size() != 0){
min_pq.pop();
}
}
//while(max_pq.size() != 0 && min_pq.size() != 0 && max_pq.top() < min_pq.top()){
//max_pq.pop();
//} min heap의 최소값이 max heap의 최대값보다 큰 경우 오류라 간주하고 삭제할려 했는데 이때는 항상 size가 0이라서 위에서 비울때 이 오류는 해결이 됨. 일부러 흔적을 남겨둠.
}
vector<int> solution(vector<string> operations) {
vector<int> answer;
for(int i = 0; i < operations.size(); i++){ // 토큰화해서 해당 명령에 따른 것을 수행함.
stringstream strStream(operations[i]);
string token1;
string token2;
getline(strStream, token1, ' ');
getline(strStream, token2, ' ');
if(token1.compare("I") == 0){
depq(input, stoi(token2));
}
else if(token1.compare("D") == 0){
if(stoi(token2) == 1){
depq(max_pop, blank);
}
else if(stoi(token2) == -1){
depq(min_pop, blank);
}
}
}
// 출력 형식 맞춰주기
if(depq_size == 0){
answer.push_back(0);
answer.push_back(0);
}
else if (depq_size == 1){
int temp = max_pq.top();
max_pq.pop();
answer.push_back(temp);
answer.push_back(temp);
}
else {
answer.push_back(max_pq.top());
answer.push_back(min_pq.top());
}
return answer;
}
스터디를 했더니 다른 풀이가 있어서 그에 대해 설명하고자 한다.
먼저 내 코드 같은 경우에는 삽입은 O(2logn) pop이 O(logn)이지만 하나의 연산에서는 무조건 O(n + logn) = O(n)이 나왔다. (허수를 없애는 연산)
다른 사람의 코드 같은 경우에는 2가지 풀이가 있었는데.
-
힙을 직접 구현해서 최소는 O(logn), 최대는 리프노드를 모두 확인해서 O(n)이 걸리는 코드, 삽입은 O(logn).
-
리스트에 정렬해서 이진 탐색으로 삽입함? (뭔가 아닌 것 같은데 잘 기억이 안남... 다른 방법이었던 것 같은데) 이 경우에는 삽입 O(n + logn) = O(n), 최소 삭제 O(n), 최대 삭제 O(1)의 비용이 든다.
(2번이 이렇게 안푸셧던것 같은데 잘 기억이 안남...)
시간 복잡도 측면에서는 내 코드가 가장 효율적이라고 생각되지만 (아닌가..?) 다양한 방법이 있던 문제였다.
