프로그래머스 Level 2 할인행사

할인행사 (프로그래머스 Level 2)

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

Map 자료구조에 대한 문제이다
비교할 때마다, 새로운 map을 생성하는 방식도 통과하였으나
더 좋은 방식이 없을까 생각해보다

Queue 처럼, 새로 들어올 인덱스의 요소만 추가하고
i - 10 번째 인덱스는 map에서 1빼주는 방식으로 바꾸었다

이전의 매번 10번씩 추가로 순회하여 Map을 만드는 방식에서
하나의 Map을 재활용하는 방식으로 바꾸어 속도가 훨씬 빨라졌다

Code

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

using namespace std;

bool isSameMap(unordered_map<string, int>& wMap, unordered_map<string, int>& tMap, const vector<string>& want)
{
	int wSize = want.size();

	for (int i = 0; i < wSize; i++)
	{
		if (tMap[want[i]] != wMap[want[i]])
		{
			return false;
		}
	}

	return true;
}

int solution(vector<string> want, vector<int> number, vector<string> discount) {
	int answer = 0;
	int wSize = want.size();

	unordered_map<string, int> wantMap;
	for (int i = 0; i < wSize; i++)
	{
		wantMap[want[i]] = number[i];
	}

	int dSize = discount.size();
	unordered_map<string, int> tempMap;

	for (int i = 0; i < 10; i++)
	{
		tempMap[discount[i]]++;
	}

	if (isSameMap(tempMap, wantMap, want))
		answer++;

	for (int i = 10; i < dSize; i++)
	{
		tempMap[discount[i]]++;
		tempMap[discount[i - 10]]--;

		if (isSameMap(tempMap, wantMap, want))
			answer++;
	}

	return answer;
}