(C++) - LeetCode (easy) 1299. Replace Elements with Greatest Element on Right Side

https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/description/

LeetCode - The World's Leading Online Programming Learning Platform

priority_queue와 map을 이용해 해결한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

1. 정답 vector ans, 내림차순으로 저장할 priority_queue pq, key에 arr원소와 value에 arr index를 저장할 map변수 arrNumIndex를 선언해줍니다.2. 각 arr의 원소를 순회하며 pq와 map에 저장해줍니다.

📔 풀이과정

pq는 현재 index의 오른쪽의 원소들 중 가장 큰 값을 top()에 저장되어 있다고 생각하면 됩니다.

1. pq.top()의 index가 현재 index i이하인 동안 pq의 원소를 pop해줍니다.

2. 여기서 arrNumIndex[pq.top()]는 해당 값의 index를 반환하므로 arr의 원소를 순회하며1. i < 오른쪽에서 가장 큰 값의 index라면 ans에 pq.top()을 push_back() 해줍니다.

 

📔 정답 출력 | 반환

ans를 반환합니다.

---

📕 Code

📔 C++

using pii = pair<int,int>;
class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        vector <int> ans;
        priority_queue <int, vector<int>, less<int>> pq;
        map<int,int> arrNumIndex;

        for(int i = 0; i < arr.size(); i++) {
            pq.push({arr[i]});
            arrNumIndex[arr[i]] = i;
        }

        for(int i = 0; i < arr.size(); i++) {
            while(pq.size() && arrNumIndex[pq.top()] <= i) pq.pop();

            if (i < arrNumIndex[pq.top()]) {
                ans.push_back(pq.top());
            }
        }
        ans.push_back(-1);
        return ans;
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.