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

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "할인 행사" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 소비자가 원하는 제품들이 연속 10일 동안 할인되는 최적의 회원가입 날짜를 찾는 것이 목적입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크 :

https://school.programmers.co.kr/learn/courses/30/lessons/131127

프로그래머스

문제 개요

XYZ 마트에서는 10일간의 회원 자격을 부여하고, 매일 한 가지 제품을 할인합니다. 이 문제에서는 소비자가 원하는 제품들이 연속 10일 동안 할인되는 최적의 회원가입 날짜를 찾는 것입니다. 주어진 제품 리스트와 할인 일정에 따라, 원하는 제품들이 모두 할인되는 날짜의 총 수를 계산하는 것이 목적입니다.

문제 해결 전략

문제를 해결하기 위한 전략은 다음과 같습니다:

1. 할인 제품 분석: 연속 10일 동안 할인되는 제품들을 분석합니다.
2. 윈도우 슬라이딩 기법 사용: 10일간의 할인 목록을 유지하면서 전체 할인 일정을 순회합니다.
3. 매칭 확인: 각 10일간의 할인 목록을 원하는 제품과 수량과 비교합니다.

코드 구현

#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

// 할인 제품과 원하는 제품의 수량을 비교하는 함수
bool Result(vector<string> &want, vector<int> &number, map<string,int> &temp) {
    int count = 0;
    for(int i = 0; i < want.size(); i++) {
        if(temp[want[i]] >= number[i]) {
            count++;
        }
    }
    return count == want.size();
}

// 메인 솔루션 함수
int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    
    for(int i = 0; i < discount.size(); i++) {
        map<string,int> temp;
        
        // 연속 10일간의 할인 제품 데이터를 temp에 저장
        for(int j = i; j < i + 10; j++) {
            if(j >= discount.size()) break;
            temp[discount[j]] += 1;
        }
        
        // 원하는 제품과 할인 제품의 매칭 여부 확인
        if(Result(want, number, temp)) {
            answer++;
        }
    }
    
    return answer;
}

코드 설명

• Result 함수는 주어진 10일간의 할인 목록(temp)과 소비자가 원하는 제품 목록(want) 및 수량(number)을 비교하여, 모든 원하는 제품이 충족되는지 여부를 반환합니다.
• solution 함수는 할인 제품 목록(discount)을 순회하며, 각 위치에서 시작하는 연속 10일간의 할인 제품 목록을 생성합니다. 생성된 목록은 Result 함수를 통해 원하는 제품 목록과 비교됩니다.
• 모든 원하는 제품이 포함된 경우, answer를 증가시켜 해당 일자를 유효한 회원가입 날짜로 계산합니다.

결론

"할인 행사" 문제는 주어진 할인 일정과 원하는 제품 목록을 효율적으로 비교하여 최적의 회원가입 날짜를 찾는 문제입니다. 윈도우 슬라이딩 기법과 맵을 사용하여 각 10일간의 할인 제품 목록을 생성하고 비교함으로써, 소비자가 원하는 제품들을 모두 할인받을 수 있는 날짜를 효과적으로 계산할 수 있습니다.