[Programmers] 할인 행사

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

프로그래머스

 

---

 

문제 해결 과정

착안

구매하고자 하는 물건의 수는 항상 10 개이며 XYZ 마트에서 10 일 연속으로 할인받는 경우만 카운팅하는 문제이므로, discount[] 배열에서 10 일 단위의 프레임을 만든 다음 한 칸씩 이동시켜보면서 조건을 만족하는지 확인한다.

 

구현

discount[] 배열의 처음 요소부터 시작하여 매번 10 개 품목에 대해 계산을 반복하면 비효율적인 시간 복잡도를 가지게 되므로, 10 일 단위의 프레임을 만들어 한 칸씩 이동시키면서 10 일 연속으로 할인하는지의 여부를 확인하였다.

• 구매 품목 및 갯수를 파악하기 위해 std::unordered_map<string, int> 클래스 형식의 컨테이너를 사용한다.
• 컨테이너에서 discount[] 배열의 처음 9 개 요소에 해당하는 값을 각각 1 씩 증가시킨다.
• $9 \le i < $ discount.size() 에 대해 아래의 과정을 반복한다.
  1. 컨테이너에서 discount[$i$] 에 해당하는 값을 1 증가시킨다.
  2. 컨테이너에 저장된 품목 및 갯수가 구매 리스트와 일치하면 answer의 값을 1 증가시킨다.
  3. 컨테이너에서 discount[$i-9$] 에 해당하는 값을 1 감소시킨다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#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> items;
    for (int i = 0; i < 9; i++)
        items[discount[i]]++;

    for (int i = 9; i < discount.size(); i++)
    {
        items[discount[i]]++;
        
        bool bSatisfied = true;
        for (int i = 0; i < want.size(); i++)
            if (items[want[i]] != number[i])
            {
                bSatisfied = false;
                break;
            }
        
        if (bSatisfied)
            answer++;
        
        items[discount[i - 9]]--;
    }
    
    return answer;
}

 

실행 결과