[C++] Programmers Lv. 2 "할인 행사"

🔵 문제 링크

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

프로그래머스

 

🔵 알고리즘

1. discount에 있는 물품 목록을 for문으로 돌면서 i + 10까지 목록을 hash에 등록한다.
2. for문 마지막에 hash에 등록된 물품들이 want, numer 데이터와 맞는지 확인한다.
3. i를 증가시키면서 반복한다.

2에서 map끼리 같은지 확인할 때, == 기호를 사용하여 손쉽게 비교할 수 있다.

STL map, unordered_map은 == 연산자를 수행하면 모든 키-값 쌍이 같을 때 true를, 하나라도 다르면 false를 반환한다.

 

🔵 전체 코드

#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> desiredItems;

    for (int i = 0; i < want.size(); i++)
        desiredItems[want[i]] = number[i];

    // i일째를 시작으로 앞으로의 10일치 일일이 확인
    for (int i = 0; i <= discount.size() - 10; i++)
    {
        unordered_map<string, int> items;

        // 현재 날짜부터 10일치 판매 물건 정보를 hash에 등록
        for (int j = 0; j < 10; j++)
        {
            string itemName = discount[i + j];
            items[itemName]++;
        }

        // 물건을 다 살 수 있는지 확인
        if (desiredItems == items)
            answer++;
    }

    return answer;
}

 

🔵 시간 복잡도

discount의 길이를 N이라 할 때, 시간 복잡도는 O(N)이다.

for문 안에 map끼리 == 연산(map의 길이가 M일 때 O(M))을 하지만 desiredItems의 최대 길이가 10이므로 크게 영향을 미치지 않는다.