[프로그래머스][C++] 할인 행사

할인 행사

문제 링크

할인 행사

분석

원하는 제품을 모두 할인 받을 수 있는 회원등록 날짜의 총 일수를 구해야 합니다.
첫 10일째 이후부터 총 일수를 구해야 합니다.

슬라이딩 윈도우(Sliding Window)를 활용할 수 있습니다.

풀이

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    
    unordered_map<string, int> wantMap;
    unordered_map<string, int> discountMap;
    
    // 원하는 상품 개수 저장
    for (int i = 0; i < want.size(); ++i)
    {
        wantMap[want[i]] = number[i];
    }
    
    // 첫 10일간의 상품 개수 저장
    for (int i = 0; i < 10 && i < discount.size(); ++i)
    {
        ++discountMap[discount[i]];
    }
    
    // 첫 윈도우 검사
    // 원하는 제품 개수와 일치하는 경우
    if (discountMap == wantMap)
    {
        ++answer;
    }
    
    // 슬라이딩 윈도우 방식으로 검사
    for (int i = 10; i < discount.size(); ++i)
    {   
        // 왼쪽 요소 제거     
        --discountMap[discount[i - 10]];
        // 특정 품목의 개수가 0개인 경우 삭제
        if (discountMap[discount[i - 10]] == 0)
        {
            discountMap.erase(discount[i - 10]);
        }
        
        // 오른쪽 요소 추가
        ++discountMap[discount[i]];
        
        // 원하는 제품 개수와 일치하는 경우
        if(discountMap == wantMap)
        {
            ++answer;
        }
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(w + n)$입니다.

• want를 순회하는 반복문 $O(w)$
• 첫 10일간의 상품 개수 저장 $O(10) \approx O(1)$
• 두 맵 값 비교 $O(w)$이지만 최대 10번의 비교이므로 $O(10) \approx O(1)$
• discount를 슬라이딩 윈도우 방식으로 검사하는 반복문 $O(n)$
• $O(w + n)$

공간 복잡도는 $O(n)$입니다.

• wantMap의 경우 최대 10개의 요소 저장 $O(10) \approx O(1)$
• discountMap의 경우 $O(n)$

테스트 1 〉 통과 (1.71ms, 4.25MB)
테스트 2 〉 통과 (13.84ms, 8.88MB)
테스트 3 〉 통과 (2.17ms, 4.45MB)
테스트 4 〉 통과 (9.10ms, 9.89MB)
테스트 5 〉 통과 (6.03ms, 6.82MB)
테스트 6 〉 통과 (1.11ms, 4.21MB)
테스트 7 〉 통과 (3.95ms, 5.13MB)
테스트 8 〉 통과 (17.73ms, 11.8MB)
테스트 9 〉 통과 (3.14ms, 4.78MB)
테스트 10 〉 통과 (8.18ms, 7.79MB)
테스트 11 〉 통과 (1.43ms, 4.16MB)
테스트 12 〉 통과 (0.01ms, 4.14MB)