[LeetCode] 2593. Find Score of an Array After Marking All Elements

https://leetcode.com/problems/find-score-of-an-array-after-marking-all-elements/description/?envType=daily-question&envId=2024-12-13

leetcode - Find Score of an Array After Marking All Elements

문제 유형: 우선순위 큐

문제 난이도: Medium

 

문제

You are given an array nums consisting of positive integers.

Starting with score = 0, apply the following algorithm:

• Choose the smallest integer of the array that is not marked. If there is a tie, choose the one with the smallest index.
• Add the value of the chosen integer to score.
• Mark the chosen element and its two adjacent elements if they exist.
• Repeat until all the array elements are marked.

Return the score you get after applying the above algorithm.

 

자연수 배열 nums가 주어진다.

score = 0부터 시작한다.

다음의 알고리즘을 적용하시오:

• 마킹되지 않은 가장 작은 정수를 고르시오. 여러 개가 있다면 앞의 인덱스걸로 고르시오.
• score에 고른 값을 누적하시오.
• 해당 요소와 양쪽에 인접한 요소들에 대해 가능하면 마킹하시오.
• 모든 요소가 마킹될 때까지 반복하시오.

 

풀이

우선순위 큐를 이용해서 그대로 구현해주면 된다.

마킹 정보를 저장하는 배열도 만들어준다.

값을 1순위로 비교하고, 인덱스를 2순위로 비교하는 최소 힙 기반의 우선순위 큐를 만들면 된다.

 

우선순위 큐가 빌 때까지 다음을 한다:

  요소를 하나 꺼내서, 인덱스가 마킹되어있다면 건너뛴다.

  그렇지 않다면, 점수를 누적하고, 인접 인덱스들에 대해 마킹처리한다.

 

최종 점수를 반환해주면 된다.

 

코드

C++

struct comp {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        if(a.first == b.first) return a.second > b.second;
        return a.first > b.first;
    }
};

class Solution {
public:
    long long findScore(vector<int>& nums) {
        int n = nums.size();
        vector<bool> mark(n, false);
        priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq; // score, idx
        for(int i = 0; i < n; ++i) {
            pq.push({nums[i], i});
        }

        long long ans = 0;

        while(!pq.empty()) {
            int point = pq.top().first;
            int idx = pq.top().second;
            pq.pop();
            if(mark[idx]) continue;
            ans += point;
            if(idx > 0) mark[idx-1] = true;
            if(idx < n-1) mark[idx+1] = true;
            mark[idx] = true;
        }

        return ans;
    }
};