할인 행사

프로그래머스 level2 C++ 연습문제 "할인 행사"

 

문제 

문제 이미지

map 을 이용했다.

1. map을 한번 만들어두고 그 뒤로는 날짜가 지나서 세일하지 않는 물품은 맵에서 빼고, 날짜가 지나서 새롭게 세일하는 품목은 넣는식으로 map을 관리. map을 만드는 for문은 한번만 돌고 그 뒤로는 돌지 않는다. -> 시간 단축을 위함.

 

2. 내가 사고자 하는 물품의 개수가 세일하는 물품의 개수보다 많으면 그 일자는 넘어감.

 

3. 세일하는 물품의 가지수가 원하는 물건의 가지수와 동일하거나 많으면 compMapMap 함수를 돈다.

이 함수는 sale하는 map을 iterator로 순회하면서 사고자하는 물건의 개수를 비교한다. (지금 생각해보니 세일 품목의 개수만 많고 찾는 물건이 없을수도 있다.. 그 예외처리도 한줄 추가하면 좋을듯하다) 원하는 물건의 개수가 세일하는 물건의 개수보다 많으면 false를 return 한다. 모든 케이스를 돌았음에도 false를 return 하지 않으면 성공한거니 최종적으로 answer에 +1 하면 된다.

 

bool compMapMap(map<string, int> _want, map<string, int> _sale)
{
    // sale map을 iter 로 돌면서 원소 개수 확인.
    map<string, int>::iterator iterSale = _sale.begin();

    for (iterSale; iterSale != _sale.end(); iterSale++)
    {
        map<string, int>::iterator iterWant = _want.find(iterSale->first);

        // 같은 요소는 찾았으나 원하는 품목의 가짓수가 slae하는 개수보다 많으면 실패
        if (iterSale->second < iterWant->second)
            return false;
    }

    // 중간에 false에 걸리지 않으면 true
    return true;
}

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    bool saleOn = false;
    int slaeOnDate = 0;

    map<string, int> WantList;
    map<string, int> SaleMap;

    bool SaleMapExist = false;

    for (int i = 0; i < want.size(); i++)
    {
        WantList.insert(make_pair(want[i], number[i]));
    }

    for (int i = 0; i < discount.size() - 9; i++)
    {

		// 세일 시작. 10일동안의 사야할 물건을 salemap안에 넣음
		if (!SaleMapExist)
		{
			int j = 0;
			while (j < 10)
			{
				if (SaleMap.find(discount[i + j]) != SaleMap.end())
				{
					// 기존 map 안에 넣으려는 원소가 이미 있을시 int 값만 올려줌
					SaleMap[discount[i + j]] += 1;
				}
				else    // 없으면 insert
					SaleMap.insert(make_pair(discount[i + j], 1));
				j++;
			}
			SaleMapExist = true;
		}
		else
		{
			// 세일맵이 이미 존재한다면 이전거 빼주고 새로운거만 더해주면 됨.
			if (SaleMap[discount[i - 1]] == 1)
			{
				SaleMap.erase(discount[i - 1]);
			}
			else
				SaleMap[discount[i - 1]] -= 1;

			if (SaleMap.find(discount[i + 9]) != SaleMap.end())
			{
				SaleMap[discount[i + 9]] += 1;
			}
			else
				SaleMap.insert(make_pair(discount[i + 9], 1));

		}

        if (SaleMap.size() < WantList.size())
            continue;

		//  map 두개 비교
		if (compMapMap(WantList, SaleMap))
		{
			// true 면 살수 있다는것.
			answer += 1;
		}

    }

    return answer;
}

 

출력 이미지 : 

 

 

map으로 관리하니 find를 이용할 수 있어서 시간단축이 엄청된다. 그리고 map을 한번 만들어두고 그걸 수정하는 방식으로 가서 더 시간초과에 걸리지 않은듯 하다.