슬라이딩 윈도우 방식

문제를 풀다보니, 내가 푼 방식이 슬라이딩 윈도우 방식 (하나씩 인덱스를 뒤로 밀어서 그 값만 바로 계산하는 방식, 계속 모든 값을 검사하는 것보다 유리) 이었다.

근데 이 방식을 제대로 쓰는 코드가 있어서 기록해둔다.

[내 코드]

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
// 찾는 함수
void Find(vector<string>& want, vector<string>& discount, map<string, int>& want_list, int index){
    string thing = discount[index];
    if (index >= discount.size()) return; // 범위 초과 방지
    // 회원기간 내에 찾았다면
    if(find(want.begin(), want.end(), thing) != want.end()) 
    {
        if (want_list[thing] > 0) { // 남은 수량이 있을 때만 처리
            want_list[thing]--;
        }
    }
}

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    int start = 0; // 새롭게 시작할 위치
    map<string, int> want_list;

    for(int i=0; i<want.size(); i++)
    {
        want_list[want[i]] = number[i]; // [banana, 3] 이런식
    }
    
    // 1. 첫 탐색
    for(int i=start; i<10; i++)
    {
        Find(want, discount, want_list, i); // 기간동안 탐색 
    }
  
    // 2. 첫 탐색 이후
    for (int start = 0; start <= discount.size() - 10; ++start)
    {
        // 2-1. map 확인
        bool canGet = true;
        for(auto w: want_list)
        {
            if(w.second != 0) 
            {
                canGet = false; // 하나라도 남아있으면 할인구매x
                break;
            }
        }
        if(canGet) ++answer; // 할인구매 가능
        
        // 2-2. 검사 마쳤으니, 다음 품목부터 보기
        if (start + 10 < discount.size()) 
        {
            // 2-2-1. 이전 품목이 원래 원하던 거였으면 map에서 뺐을 것이므로
            if (find(want.begin(), want.end(), discount[start]) != want.end()) 
            {
                want_list[discount[start]]++; // 다시 추가
            }
            // 2-2-2. 새롭게 검사할 품목 하나만 Find함수 이용
            Find(want, discount, want_list, start+10);
        }
        // 다시 돌아서 map확인 작업
    }
    return answer;
}

[최적화된 코드]

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

bool isSatisfied(map<string, int>& want_list) {
    for (auto& w : want_list) {
        if (w.second > 0) return false;
    }
    return true;
}

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    map<string, int> want_list;

    // 초기 맵 생성
    for (int i = 0; i < want.size(); i++) {
        want_list[want[i]] = number[i];
    }

    // 슬라이딩 윈도우 방식으로 확인
    for (int start = 0; start <= discount.size() - 10; ++start) {
        // 현재 상태를 복사해서 사용
        map<string, int> current_list = want_list;

        // 10일 간의 할인 상품 확인
        for (int i = start; i < start + 10; ++i) {
            if (current_list.find(discount[i]) != current_list.end()) {
                current_list[discount[i]]--; // 원하는 상품일 경우 수량 감소
            }
        }

        // 모든 원하는 상품의 수량이 만족되면 구매 가능
        if (isSatisfied(current_list)) {
            answer++;
        }
    }

    return answer;
}

위 코드의 핵심 변경점

맵 복사(current_list):

매번 새롭게 10일 간의 상태를 검사할 때, 원본 맵(want_list)을 복사해서 사용.
이렇게 하면 각 슬라이딩 윈도우에서 맵의 초기 상태를 유지할 수 있음.

isSatisfied 함수:

맵의 값이 모두 0 이하인지 확인하는 별도의 함수를 구현하여 코드 가독성 향상.

루프 논리 단순화:

슬라이딩 윈도우 범위를 명확히 설정하고, 복잡한 조건문을 제거.

시간복잡도와 효율성 측면에서 GPT한테 물어보니.. (ㅎ)

비교 결과

• 시간 복잡도:
  두 방식 모두 시간 복잡도는 동일하게 𝑂(𝑛𝑚), O(nm)입니다.

• 상수 계수 측면:
  현재 코드는 슬라이딩 윈도우 방식으로 새로 추가된 항목과 제거된 항목만 처리하므로, 매번 10개의 항목을 모두 처리하지 않습니다. 따라서 실제로 반복당 처리 작업량이 적습니다.
  처음부터 10개를 매번 검사하는 방식은 매번 10개의 항목을 처리하므로 상수 계수 측면에서 느립니다.

• 결론
  현재 코드가 슬라이딩 윈도우 방식을 사용하여 효율적으로 동작하므로 더 유리합니다. 처음부터 10개씩 다시 검사하는 방식은 비효율적이고, 반복마다 처리량이 더 많습니다. 따라서 현재 코드가 시간 복잡도 측면에서 더 우수합니다.