[백준 1202] 보석 도둑

 그동안 포트폴리오랑 자기소개서를 작성하느라 공부를 많이 하지 못했는데, 어느정도 틀은 완성한 것 같아서 조금 여유가 생겼다. 아직 고칠 부분이 많지만 이제 다시 공부를 병행할 수 있을 것 같다. 더군다나 알고리즘 문제는 부트캠프 최종 프로젝트 기간동안 손을 놨다가 오랜만에 푸는 것이고, 이렇게 내일배움캠프가 아닌 카테고리에 개별 포스트로 작성하는 것도 처음이기 때문에 감회가 새롭다.

 

 

 문제가 심플하면서 묻고 있는 것이 명확하다. 그런데 알고리즘 문제를 너무 오랜만에 풀었더니 이 문제에서도 꽤 난항을 겪었다. 당연히 보석과 가방 리스트를 그대로 이용하게 되면 절대 제한 시간 안에 풀 수 없다. 그래서 가방을 내림차순으로 정렬하고, 우선순위 큐를 통해 보석을 가치가 크면서 무거운 보석이 먼저 나오도록 해두고 접근해봤다.

 하지만 여러가지 방법을 고민해봐도 시간 복잡도가 O(NK)에 이르는 로직밖에 떠오르지 않았다. 그래서 자료구조를 다르게 적용하려고 고민한 끝에 간단한 로직으로 해결할 수 있었다.

 

1. 보석과 가방을 각각 무게와 담을 수 있는 무게를 기준으로 오름차순 정렬한다.

2. 가방 리스트를 처음부터 하나씩 탐색하면서, 각 가방의 무게보다 작거나 같은 보석을 모두 우선순위 큐에 집어 넣는다.(보석 리스트는 이미 정렬되어 있으므로, 앞에서부터 하나씩 탐색하면 된다. 우선순위 큐는 보석의 가치가 클수록 우선순위가 커지도록 한다.)

3. 담을 수 있는 보석을 모두 우선순위 큐에 넣었다면, top을 가져와 보석 가격 총합에 더한다.

4. 남은 가방들도 같은 방식으로 탐색을 진행하고, 당연히 내부 로직에서 보석 리스트를 탐색할 때는 앞에서 우선순위 큐에 넣었던 보석은 탐색할 필요가 없다.

 

 위와 같은 심플한 로직이면 O(K logN)으로 해결할 수가 있기 때문에, 시간 초과에 걸리지 않고 통과할 수 있었다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std; 

int n, k;
pair<int, int> gemList[300000];
int bagList[300000];

int main() {
    cin >> n >> k;

    for(int i=0; i<n; i++) {
        cin >> gemList[i].first >> gemList[i].second;
    }

    for(int i=0; i<k; i++) {
        cin >> bagList[i];
    }

    priority_queue<int> pq;
    sort(gemList, gemList+n);
    sort(bagList, bagList+k);
    long long sum = 0;
    int gemInd = 0;
    for(int i=0; i<k; i++) {
        int bag = bagList[i];
        while(gemInd<n && gemList[gemInd].first<=bag) {
            pq.push(gemList[gemInd].second);
            gemInd++;
        }

        if(!pq.empty()) {
            sum += pq.top();
            pq.pop();
        }
    }

    cout << sum;
}

 

 

 하도 코틀린만 만지다가 오랜만에 C++로 코드를 작성하니 어색한 느낌도 있었다. 특히 VS code임에도 불구하고 자꾸 안드로이드 스튜디오의 단축키에 손이 갔다...