말하는감자의 공부기록

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

❗풀이방법

: 살 수 있는 품목을 저장하고 또 해당 품목이 몇개가 있는지 저장해야 함

=> map 사용 

1. 입력받은 want 와 number 이 각각 key와 value가 되어 map에 저장됨

map<string, int> shoppingCart;
for (int i = 0; i < want.size(); i++) 
{
    shoppingCart.insert( {want[i], number[i]});
}

2. discount 배열을 돌면서 10개씩 map에 저장후, 위에서 저장한 map과 비교함

for (int i = 0; i <= discount.size() - 10; i++) 
{
	map<string, int> innerMap;

	// 1. 저장
	for (int j = i; j < i + 10 ; j++) 
	{
		innerMap[discount[j]]++;
	}

	// 2. shoppingCart와 비교 , 다른게 있으면 flag를 false로 변경
	bool flag = true;
	for (map<string, int>::iterator it = innerMap.begin(); it != innerMap.end(); it++)
	{
		string key = it->first;
		int value = it->second;
		
		if (shoppingCart[key] != value)
			flag = false;
	}

	// 3. want만큼 구매 가능하면 answer을 + 해줌
	if (flag)
		answer++;

}

- 문제에서 "10일 연속으로 일치" 라고 적혀져 있었는데 이 부분을 못보고 number 를 더하고 있었다. 

문제를 잘 읽자 ! 

- for문 안에서 break조건

for (map<string, int>::iterator it = innerMap.begin(); it != innerMap.end(); it++)
{
	string key = it->first;
	int value = it->second;
	
	// 1. shoppingCart안에 key가 있는지 검사 
	if (shoppingCart.find(key) == shoppingCart.end())
	{
		flag = false;
		break;
	}

	// 2. key에 대한 value가 같은지 검사 
	if (shoppingCart[key] != value)
	{
		flag = false;
		break;
	}
}

(1) map에 key가 있는지 검사하는 조건을 넣어도 제출된다.

(2) 조건을 만족했을 때 break를 넣고 안 넣고는 문제 제출에 큰 영향을 받지 않는다.!

- 원래 생각한 로직

(1) 처음부터 10개를 map에 넣는다.

(2) 기준이 되는 map과 비교를 한다 (코드상 shoppingCart)

(3) 맨 처음 나온 품목(key)에 해당하는 value를 -1 한다. (빨간색 박스에 해당하는 품목) 

(4) 그리고 다음 품목(key)에 해당하는 value를 +1 한다. (파랑색 박스에 해당하는 품목)

(5) (2)번과 똑같이 기준에 map과 비교를 한다.

=> "10일 연속으로 일치"라는 문장을 이해하기전에 코드를 짰다가, 안되서 포기했던 로직이다. 

문제를 이해했으니 추후 다른 방식으로 풀어서 제출해보겠다.

✅풀이방법

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    int wholeCount = 10;

    map<string, int> shoppingCart;
    map<string, int> my;

    bool flag = false;

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

    for (int i = 0; i <= discount.size() - 10; i++) 
    {
        map<string, int> innerMap;

        for (int j = i; j < i + 10 ; j++) 
        {
            innerMap[discount[j]]++;
        }

        bool flag = true;
        for (map<string, int>::iterator it = innerMap.begin(); it != innerMap.end(); it++)
        {
            string key = it->first;
            int value = it->second;

            // 갯수가 다르면 
            if (shoppingCart[key] != value)
            {
                flag = false;
                //break;
            }
        }

        if (flag)
            answer++;
    }

	
    return answer;
}

https://github.com/kimYouChae

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

❗풀이방법

1. unordered_map을 사용하여 key를 추가한다.

key가 중복되면 value값을 증가시킨다

#include <unordered_map>

unordered_map<int, int> map;
    
for (int i = 0; i < tangerine.size(); i++) 
{
    auto findIter = map.find(tangerine[i]);
    if (findIter == map.end())
    {
        map.insert({ tangerine[i], 1 });
    }
    else
        map[tangerine[i]]++;
}

2. value값으로 정렬하기 위해서 vector로 값을 복사한다.

	// unordered_map 안에 value값으로 정렬해야함 
	// 1. map의 원소를 vector로 복사
	// -> iterator가 가리키는 값을 복사해서 저장함 (pair가 포인터일 필요는 없음)
	vector<pair<int, int>> vec(map.begin(), map.end());

3. pair.second값을 기준으로 내림차순 정렬한다.

#include <algorithm>

bool compare(pair<int,int>& tu1, pair<int,int>& tu2)
{
	// 큰순으로 정렬
	return tu1.second > tu2.second;
}

sort(vec.begin() , vec.end() , compare );

4. pair.second 값 즉 갯수를 더하면서 총 갯수 (k)값이 넘는지 검사한다

	int sum = 0;
	for (int i = 0; i < vec.size(); i++) 
	{
		if (sum >= k) 
		{
			break;
		}
	
		sum += vec[i].second;
		answer++;
	}

❗전체코드

bool compare(pair<int,int> tu1, pair<int,int> tu2)
{
	// second가 큰순으로 정렬
	return tu1.second > tu2.second;
}

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    
    unordered_map<int, int> map;
    
   	for (int i = 0; i < tangerine.size(); i++) 
	{
		auto findIter = map.find(tangerine[i]);
		if (findIter == map.end())
		{
			map.insert({ tangerine[i], 1 });
		}
		else
			map[tangerine[i]]++;
	}

	// unordered_map 안에 value값으로 정렬해야함 
	// 1. map의 원소를 vector로 복사
	// -> iterator가 가리키는 값을 복사해서 저장함 (pair가 포인터일 필요는 없음)
	vector<pair<int, int>> vec(map.begin(), map.end());

	sort(vec.begin() , vec.end() , compare );

	int sum = 0;
	for (int i = 0; i < vec.size(); i++) 
	{
		if (sum >= k) 
		{
			break;
		}
	
		sum += vec[i].second;
		answer++;
	}
	
    return answer;
}

로직 생각하는데는 얼마 안 걸렸는데 c++ 로 한다고 STL사용법이나 문법적으로 찾아본다고 시간이 많이 걸렸다....

https://github.com/kimYouChae