[Leetcode/C++] 239_Sliding Window Maximum

문제는 다음과 같습니다.

일단 난이도 hard에서 좀 쫄았습니다. ㅋㅋ
하지만 바로 정신차리고 문제를 읽었습니다.

문제는 간단합니다.
딱봐도 일단 슬라이딩윈도우, kmp알고리즘?이 생각났습니다.

오른쪽으로 한 칸씩 이동하면서 주어진 k 사이즈에서 최댓값을 찾아서 결과벡터에 차곡차곡 담으면 됩니다.

이 문제의 핵심은 k 사이즈를 돌 때, 처음이 아닌 이상 계속 반복해서 돌 필요가 없다는 것입니다.

어떻게 반복을 줄이는가가 관건인 문제입니다.

풀이1 : priority_queue 이용

먼저 제가 처음으로 푼 풀이는 priority_queue를 이용한 풀이입니다.
전 정말 ,, 연산자 오버로딩된 priority_queue가 정말 활용도가 높다고 생각합니다.. 만능 그 자체입니다

먼저, 배열의 인덱스 그리고 그 값을 pair로 묶어 priority_queue에 저장합니다.

priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> pq; // <idx, nums[idx]> 저장

이 priority_queue의 우선순위는 따로 정의를 했는데요,
우선순위는 다음과 같습니다.

• nums[idx]가 큰 순서대로 정렬
• nums[idx]가 같다면 idx가 큰 순서대로 정렬 (최신임을 의미)

구조체 cmp로 정의하고, priority_queue의 세 번째 인자에 넣었습니다.
구조체 cmp는 다음과 같습니다.

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

그리고 핵심은 다음과 같습니다.

1. 순회를 할 때에 우선순위큐에 값을 먼저 넣습니다.
2. 그리고 그 순회의 순서에 맞추어 결과벡터 res에도 그 순서에서의 사이즈 k에 해당하는 값에서 최댓값을 찾아 넣어주어야 합니다.

두 번째를 구할 때에는

우선순위 큐의 결과의 idx가 순회하는 i-k보다 작거나 같을 경우에는 해당 k 사이즈의 범위에 벗어나므로

이에 해당하는 값은 pop을 해주어야 합니다.

while(pq.top().first <= i-k){
    pq.pop();
}

이어서 전체 코드는 다음과 같습니다.

class Solution {
public:
    struct cmp{
        bool operator() (pair<int, int>&a, pair<int, int>&b){
            if(a.second==b.second){
                return a.first < b.first;
            }
            else{
                return a.second < b.second;
            }
        }
    };
    
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res; // 결과벡터
        priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> pq; // <idx, nums[idx]> 저장
        int i;
        
        // 첫 번째 순회만 예외처리
        for(i=0; i<k; i++) pq.push({i, nums[i]});
        res.push_back(pq.top().second);
        
        // 두 번째 이후부터
        for(; i<nums.size(); i++){
            pq.push({i, nums[i]});
            while(pq.top().first <= i-k){
                pq.pop();
            }
            res.push_back(pq.top().second);
        }
        return res;
    }
};

다른 사람들이 풀이가 매우 궁금한데요
일단 스터디가 4시간 뒤라,
다른 풀이는 스터디가 끝난 이후에 복습하면서 올리겠습니다.