[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;
}
}
};
그리고 핵심은 다음과 같습니다.
- 순회를 할 때에 우선순위큐에 값을 먼저 넣습니다.
- 그리고 그 순회의 순서에 맞추어 결과벡터 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시간 뒤라,
다른 풀이는 스터디가 끝난 이후에 복습하면서 올리겠습니다.
Author And Source
이 문제에 관하여([Leetcode/C++] 239_Sliding Window Maximum), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ssssujini99/LeetcodeC-239Sliding-Window-Maximum저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)