[leetcode] 239. Sliding Window Maximum

간만에 하드 문제를 풀어보았다.

문제를 보고선 바로 아래와 같은 풀이를 생각했다.

타임아웃이 예상되었지만, 자비로운 리트코드기에 굉장히 떨어지는 성능으로 통과 시켜줄거라 생각햇지만,, 역시 실패

 

소스 보시면 아시겠지만 단순하게 우선순위큐를 계속 생성해서 max 값을 리턴하게 해두었다.

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ret;
        for(int i = 0; i <= nums.size() - k; i++){
            priority_queue<int, vector<int>, less<int>> hash(
                nums.begin() + i, nums.begin() + i + k
            );

            ret.push_back(hash.top());
        }
        
        return ret;
    }
};

 

딱봐도 슬라이딩 윈도우로 푸는 것이었으나,, 머리가 안돌아가서 Discuss를 참조하였다.

역시 언제나 풀이는 너무나 간단한데,, 왜 나는 이것도 못푸나 싶다 

 

진짜 오랜만에 deque를 사용하였고 윈도우를 움직일떄의 최대값을 que의 front에 위치시킨다는 개념으로 풀이한 방식이다.

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ret;
        deque<int> que;
        
        for(int i = 0; i<nums.size(); i++){
            while(que.size() > 0 && que.back() < nums[i]){
                que.pop_back();
            }
            que.push_back(nums[i]);
            
            if(i >= k - 1){
                ret.push_back(que.front());
                if(que.front() == nums[i - k + 1]){
                    que.pop_front();
                }
            }
        }
        
        return ret;
    }
};

 

while문에서 최악의 경우 시간을 좀 잡아먹긴하겟지만, 결과를 보니 나름 준수한 편인 것 같다.

최적해를 찾는건 다음으로,,,,,,,