슬라이딩 윈도우

할인행사

프로그래머스

 

해당 문제를 풀다가 슬라이딩 윈도우에 대해서 알게 되었다.

우선 처음 내 생각은 완전 탐색으로 풀어보는 것이었다.

 

#include<bits/stdc++.h>

using namespace std;

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    
    // 맵 사용 key : 품목 이름 , value : 개수 
    unordered_map<string, int> wanted;
    unordered_map<string, int> copy;
    
    for(int i=0;i<want.size();i++) wanted[want[i]] = number[i];
    
    // 전부 다 찾아봐야될 것 같으니 일단 완전탐색
    // 시작일로부터 10일동안 원하는 상품을 모두 살 수 있는지 체크 후 살수 있다면 answer + 1
    
    // 길이가 길어서 효율적으로 보는게 좋을까 ? 일단 브루트포스로 풀어보자
    copy = wanted;
    for(int i=0;i<discount.size() - 9;i++)
    {
        int cnt = 0;
        for(int j=i;j<i + 10;j++)
        {
            // 주어진 기간내에 물품을 모두 사야하므로 만약 원치 않는 할인 물품일 경우 
            // 원하는대로 못사기 때문에 바로 아웃
            if (copy.count(discount[j]) == 0) break;
            copy[discount[j]]--;
            if (copy[discount[j]] == 0) cnt++;
            if (copy[discount[j]] < 0) break;
        }
        // 원하는 상품을 모두 구매한 경우 cnt가 올라가기 때문에
        // cnt가 원하는 물품의 길이와 같다면 그건 모든 물품을 구매한 경우임
        if (cnt == want.size()) answer++;
        copy = wanted;
    }
    
    
    return answer;
}

 

주석을 보면 내가 생각한 흐름이 보일 것이다.

할인하는 날짜는 정해져 있고 차례대로 10개씩 살펴보면 풀릴 문제라고 생각했다. 하지만 효율성 부분에서 문제가 생기지 않을까 했는데 아무 문제 없이 성공했다.

 

하지만 좀 더 효율적인 방법을 찾고 싶어서 고민을 해봤는데 가장 먼저 떠올린 방법이 어차피 정해진 10개를 계속 살펴봐야 한다면 시작 인덱스부터 끝 인덱스까지 정해진 틀을 가지고 같은 조건으로 계속 살펴볼 수 없을까 생각했다. 바로 투 포인터 방식을 활용하는 것이었다.

 

아니나 다를까 비슷한 알고리즘이 있었다.

 

슬라이딩 윈도우는 배열을 특정 크기만큼 잘라서 데이터를 저장하고 그 저장한 값을 기반으로 문제를 살펴보는 기법이라고 생각하면 편하다.

 

앞부분의 인덱스를 하나 증가하면서 윈도우에 저장된 앞부분 값을 하나 빼주고

뒷부분의 인덱스를 하나 증가하면서 윈도우에 저장할 뒷부분 값을 하나 늘려주면서

조건에 해당하는지 비교하면 된다.

 

주의할 점은 제일 끝 인덱스가 살펴볼 배열을 넘어가면 종료해야 한다는 점이다. 인덱스를  잘 관리해줘야 한다. 이것 때문에 계속 헤맸다.

 

코드로 살펴보자.

 

#include<bits/stdc++.h>

using namespace std;

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    
    // 맵 사용 key : 품목 이름 , value : 개수
    // 비교할 wanted와 잘라서 볼 window 사용
    unordered_map<string, int> wanted;
    unordered_map<string, int> slidingwindow;
    
    for(int i=0;i<want.size();i++) {
        wanted[want[i]] = number[i];
        slidingwindow[want[i]] = 0;
    }
    
    // 쇼핑할 물품인 경우에만 체크해줄 것
    for(int i=0;i<10;i++) if (slidingwindow.count(discount[i])) slidingwindow[discount[i]]++;
    
    // 윈도우의 시작인덱스와 끝인덱스
    int startidx = 0;
    int lastidx = 9;
    
    // 종료조건 설정
    while(lastidx < discount.size())
    {
        if (slidingwindow == wanted) answer++;
        lastidx++;
        if (lastidx == discount.size()) break;
        if (slidingwindow.count(discount[startidx])) slidingwindow[discount[startidx]]--;
        if (slidingwindow.count(discount[lastidx])) slidingwindow[discount[lastidx]]++;
        startidx++;
    }
    
    return answer;
}

 

나는 기존 코드를 활용하느라 unordered_map을 그대로 사용했지만, 벡터나 다른 어떤 것이든 상관없을 것이다.

윈도우에 저장된 데이터 값으로 실제 원하는 품목을 비교해볼 수만 있으면 된다.

 

다만 내 경우 반복문 내에 break문을 설정해줬는데 반복문의 종료 조건 만으로는 계속해서 배열의 범위를 벗어나 버려서 오류가 계속 발생했다.... 무조건 특정 크기의 상태를 유지해야 했기 때문에 검사 후 끝부분의 인덱스가 벗어나는 문제여서 검사 후 종료 조건을 한 번 더 체크하게 만들었다.

 

뭔가 깔끔하지 못한 코드인 거 같아서 조금 더 고민을 해보기로 했다. 중간에 조건문 없이 유연하게 동작하게 만들고 싶었다.

문제가 되는 것이 인덱스를 늘린 다음 범위를 벗어난 인덱스를 체크하려고 하는 것이 문제이므로 인덱스를 늘리기 전에 체크하면 되지 않을까 생각했는데 그게 맞았다.

 

#include<bits/stdc++.h>

using namespace std;

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    
    // 맵 사용 key : 품목 이름 , value : 개수 
    unordered_map<string, int> wanted;
    unordered_map<string, int> slidingwindow;
    
    for(int i=0;i<want.size();i++) {
        wanted[want[i]] = number[i];
        slidingwindow[want[i]] = 0;
    }
    
    // 0 ~ 8 번까지만 담기
    for(int i=0;i<9;i++) if (slidingwindow.count(discount[i])) slidingwindow[discount[i]]++;
    
    // 뒷부분의 인덱스로 관리 9 10 11 12 13 으로 진행
    int idx = 9;
    for(;idx<discount.size();idx++)
    {
        if (slidingwindow.count(discount[idx])) slidingwindow[discount[idx]]++;
        if (slidingwindow == wanted) answer++;
        if (slidingwindow.count(discount[idx - 9])) slidingwindow[discount[idx - 9]]--;
    }
    
    return answer;
}

 

시간 효율을 따져보려고 했는데 생각보다 큰 차이가 나지는 않을 것 같다. 상수만큼 살펴보는 것이기 때문에 아마 살펴보는 값이 커지면 유의미한 차이가 있을 것으로 생각된다.