[프로그래머스] 코딩테스트 고득점 Kit 힙 C++ (더 맵게, 디스크 컨트롤러, 이중우선순위큐)

1️⃣ 더 맵게

프로그래머스

• 생각 흐름
  • 일단 내림차순 정렬을 해서 pop_back을 사용하자 (vector 사용)
  • pre, now를 선언하고,
  • pre가 K보다 작으면 now랑 섞기

코드1 - 오답

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(int a, int b){
    return a > b;
}

int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    sort(scoville.begin(), scoville.end(), compare);
    
    for (int i=scoville.size()-2;i>=0;i--){
        int pre = scoville[scoville.size()-1];
        int now = scoville[i];
        if (pre < K){
            answer++;
            scoville.pop_back();
            scoville.pop_back();
            
            int temp = pre + now*2;
            scoville.push_back(temp);
        }
        sort(scoville.begin(), scoville.end(), compare);
    }
    
    
    return answer;
}

 

효율성 빵점짜리 코드..^^ 테스트 케이스도 몇 개 틀렸다..ㅎㅎ

for문 안에서 계속 sort를 하고 있어서 효율성이 테스트가 모두 실패한 것 같다.

vector를 sort함수로 정렬할 때 시간 복잡도가 O(nlogn)이라 위 코드의 시간 복잡도는 O(n)*O(nlogn)이 될 것이다. 

코드를 작성하면서 마음에 걸리긴 했지만 그냥 작성했으나 효율성 테스트도 있는지 몰랐다ㅎ.ㅎ

게다가 정확성 테스트도 몇 개 틀렸으니 아예 다른 자료구조를 사용해야겠다는 생각을 했다.

 

코드2 - 정답

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue <int, vector<int>, greater<int>> pq(scoville.begin(), scoville.end());
    
    while (pq.size()>1 && pq.top() < K){
        int first = pq.top();
        pq.pop();
        int second = pq.top();
        pq.pop();
        pq.push(first+(second*2));
        answer++;
    }
    
    if (pq.top()<K) return -1;
    
    return answer;
}

 

 

정답 코드에서는 우선순위 큐를 사용했다. 시간 복잡도를 줄여야겠다는 생각을 하고 힙의 시간 복잡도는 O(nlogn)이므로 효율성이 크게 개선될 것이라 생각했다.

scoville 벡터에 있는 값을 모두 priority_queue로 복사해오는 동시에 greater를 사용해 자료구조는 최소 힙으로 선택했다.

pq에 2개 이상의 원소가 있을 때, 그리고 pq의 가장 작은 값이 K보다 작으면 스코빌지수를 섞어주는 연산을 진행했다.

pq는 push 연산이 이뤄질 때마다 while문 안에 따로 sort를 해주지 않아도 되어 sort는 따로 작성해주지 않았다.

 

💡 우선순위 큐의 기본 개념과 활용 방식
     1. 최대 힙 vs 최소 힙
         - 최대 힙: priority_queue<int, vector<int>> pq;
         - 최소 힙: priority_queue<int, vector<int>, greater<int>> pq;
     2. 시간 복잡도
         - push, pop 연산의 시간 복잡도: O(logn)
     3. 힙의 활용 예시
         - 최소 비용 문제: 다익스트라 알고리즘에서와 같이 최단 거리 계산을 위해 우선순위 큐를 사용해 탐색할 노드를 거리 기준으로 정렬이 가능
         - 가장 큰, 작은 요소 N개 유지
         - 병렬 정렬 및 데이터 병합
         - 스케줄링 문제: 작업을 우선순위에 따라 처리할 때도 유용, 작업의 시작이나 종료 시간을 추적할 때 유용

💡 힙의 종류
     0. 개념
         - 우선순위 큐를 구현할 때 주로 사용되는 완전 이진 트리 기반의 자료구조로, 모든 부모 노드의 값이 자식 노드의 값보다 크거나 작은 규칙을 가짐
     1. 힙의 종류
         - 최대 힙: 부모 노드의 값이 항상 자식 노드 값보다 크거나 같은 트리
         - 최소 힙: 부모 노드의 값이 항상 자식 모드 값보다 작거나 같은 트리
     2. 힙의 특징
         - 완전 이진 트리: 트리의 모든 레벨이 꽉 차 있고, 마지막 레벨만 왼쪽부터 순서대로 채워져 있는 완전 이진 트리 형태를 유지
         - 빠른 최대, 최소 값 추출: 힙은 루트 노드에 최소, 최대값이 있어 O(1)의 시간으로 빠르게 찾을 수 있음
         - 삽입과 삭제 효율성: 힙의 삽입 및 삭제 연산은 트리의 균형을 맞추는 과정에서 O(logn)의 시간 복잡도를 가짐

 

---

 

2️⃣ 디스크 컨트롤러

프로그래머스

 

• 생각 흐름
  • 작업의 소요 시간 기준으로 오름차순 정렬하기
  • 현재 시간을 나타내는 time 변수, 평균 대기 시간 계산을 위한 변수 count
  • jobs 벡터가 비어있지 않는 동안 반복문을 돌며
  • 작업이 요청되는 시점이 time보다 작을 경우 time에 소요 시간 더해주고, answer에는 대기 시간을 더해주고, 수행된 작업은 erase하기

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 작업 소요 시간이 작은 것부터 정렬
bool compare(vector<int> a, vector<int> b){
    return a[1] <= b[1];
}

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int time = 0;
    int count = jobs.size();
    
    sort(jobs.begin(), jobs.end(), compare);
    
    while (!jobs.empty()){
        for (int i=0;i<jobs.size();i++){
            if (jobs[i][0] <= time){
                time += jobs[i][1];
                answer += (time - jobs[i][0]);
                jobs.erase(jobs.begin()+i);
                break;
            }
            if (i==jobs.size()-1) time++;
        }
    }
    return answer/count;
}

 

우선순위 큐를 사용하지 않고 문제를 풀 수 있었다. jobs 벡터를 작업 소요 시간이 작은 것부터 오름차순 정렬했고, erase함수를 통해 특정 작업을 벡터에서 삭제해주면서 반복문을 돌았다.

 

---

 

3️⃣ 이중우선순위큐

프로그래머스

 

#include <string>
#include <vector>
#include <set>

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    multiset<int> ms;
    
    for (auto operation: operations){
        if (operation[0]=='I'){
            int num = stoi(operation.substr(2));
            ms.insert(num);
        } else if (!ms.empty()){
            if (operation[2]=='-'){ // 최소 삭제
                ms.erase(ms.begin());
            } else { // 최대 삭제
                ms.erase(--ms.end());
            }
        }
    }
    
    if (ms.empty()){
        answer.push_back(0);
        answer.push_back(0);
    } else {
        answer.push_back(*(--ms.end()));
        answer.push_back(*ms.begin());
    }
    
    return answer;
}

 

min_heap, max_heap을 사용해서 문제를 해결해보려 했으나... 너무 복잡해져서 그냥 multiset을 사용하기로 했다.

문제에서 주어진대로 I면 원소를 추가하고 D면 최소 혹은 최대 원소를 삭제했다.

multiset이 비어있다면 [0,0]을 직접 추가해줬고, 비어있지 않다면 가장 큰 값과 가장 작은 값을 push_back 해주었다.

 

💡 multiset
     1. 헤더: #include <set>
     2. 특징
         - 자동 정렬
         - 삭제 위치가 자유로움
         - set과 다르게 중복값을 허용함
         - multiset<int, greater<int>> ms; 는 내림차순, 오름차순은 multiset<int, less<int>> ms;인데 생략 가능
         - 가장 마지막 원소 삭제 시에는 --ms.end()를 해야 함 (bc. ms.end()는 가장 마지막 원소 다음의 빈 곳을 가리키고 있음!)
     3. 삽입: ms.insert(요소)
     4. 삭제: ms.erase(요소)
     5. 탐색: ms.find(요소)
     6. 개수 조회: ms.count(요소)