말하는감자의 공부기록

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/12985

❗풀이방법

:  N이 범위가 넓어서 for문은 사용하면 안 되겠다고 생각했다.

: 대진표를 그려보면 이렇게 된다. 
1번과 2번은 두번째에 1이 되고, 

3번과 4번은 두번째에 2가 되고,

5번과 6번은 두번째에 3이 되고............

N-1과 N번은 두번째에 ( N-1 + 1 ) / 2 번째가 된다.

: 같은 '그룹'에 속해있는지 검사방법

-> 위의 사진에서 마지막에는 [1,2] 번이 대결하게 된다.

-> 한번더 순서를 정했을 때, 둘 다 1번이 된다. -> 같은 그룹에 속해있다. 

❗틀린 시도 

int aOrder = a;
int bOrder = b;

while (true) 
{
	if (abs(aOrder - bOrder))
	{
		break;
	}

	// a가 짝수/훌수이면?
	if (aOrder % 2 == 0)
		aOrder /= 2;
	else
		aOrder = aOrder / 2 + 1;

	// a가 짝수/훌수이면?
	if (bOrder % 2 == 0)
		bOrder /= 2;
	else
		bOrder = bOrder / 2 + 1;

	//cout << aOrder << " / " << bOrder << endl;
	answer++;
}

: while문을 break하는 조건문에서,

A순서와 B순서의 차이가 1이면 만난다,라고 생각했는데

만약 A가 2번, B가 3번 일 때는 같은 그룹이 아닌데도 조건에 만족하기 때문에 테스트케이스에서 틀렸었다.

[1,2][3,4]로 그룹이 이루어져 있는데, A-B가 1은 맞지만 같은 그룹이 아니다.

int solution(int n, int a, int b)
{
    int answer = 0;

    int aOrder = a;
    int bOrder = b;

    while (true) 

    {
        // 예외 : 처음에 2, 3이면 오류남, [1,2][2,3] 그룹이 이렇게 되어야함
        // 만약 둘이 붙어있는 그룹이면 [1,2] -> 한번 더 순서를 정했을 때 같은 순서가 된다.
        if (aOrder == bOrder)
        {
            break;
        }

        // 3,4일 때 (3+1)/2 = 2, (4+1)/2=3
        aOrder = (aOrder + 1) / 2;
        bOrder = (bOrder + 1) / 2;

        answer++;
    
    }

    return answer;
}

: [3,4]가 대전을 했을 때, 번호가 홀수일 때 짝수일 때로 조건을 나눴었다.

그런데 먼저 +1을 더하고 2로 나누게 되면 홀수와 짝수 둘 다 올바른 순서를 구할 수 있다.

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

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

❗풀이방법

1. 한 단어의 끝과 다음 단어의 처음이 같아야 한다.

// 첫번째 글자의 마지막 char
string endstring = words[0];
char endchar = endstring[endstring.size() - 1];

// 두번째 부터 검사 
for (int i = 1; i < words.size(); i++)
{
    // ..... 
        
    // endchar 초기화 해주기 
    endchar = words[i][words[i].size() - 1];
}

2. 중복되는 단어가 들어오면 안된다

✅  c++의 set 사용 

set<string> set;

auto temp = set.insert(words[i]);

: key값은 중복이 되지 않음

: set에 insert를 하게되면 pair<iterator , bool >형태로 return된다

: pair.first는 삽입한 원소(iteroator 타입), pair.second는 성공여부 

❗전체코드

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main()
{
	set<string> set;
	int turn = 1;	// 몇번째 턴이 돌았는지
	int personindex = 1;

	bool flag = false;	// 중복이 있었는지 

	// 첫번째 글자의 마지막 char
	string endstring = words[0];
	char endchar = endstring[endstring.size() - 1];

	set.insert(words[0]);

	// 두번째 부터 검사 
	for (int i = 1; i < words.size(); i++)
	{
		// 한바퀴 돌면
		if (i % n == 0)
			turn++;
		// 몇번째 사람인지
		if (personindex == n)
			personindex = 0;
		personindex++;

		auto temp = set.insert(words[i]);

		if (endchar != words[i][0] || temp.second == false)
		{
			flag = false;
			break;
		}

		endchar = words[i][words[i].size() - 1];
	
	}

	if (flag) 
	{
		answer.push_back(0);
		answer.push_back(0);
	}
	else 
	{
		answer.push_back(personindex);
		answer.push_back(turn);
	}
}

https://github.com/churush912837465

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

[C++][프로그래머스][Lv2] 12980. 점프와 순간이동

 ❗풀이방법

1. 배터리를 최소로 사용하려면  ? ▶️순간이동을 최대한 많이 해야한다.

예시1) 거리가 5일 때 

: 2에서 순간이동 한 뒤 1칸을 점프하면 된다.

: 2는 ? 1에서 순간이동 하면된다.

: 1은? 0에서 한칸 점프하면 된다. 

예시2) 거리가 6일 때

: 3에서 순간이동 하면 된다. 

: 3은 ? 2에서 1칸을 점프하면 된다.

: 2는 ? 1에서 순간이동 하면 된다.

: 1은 ? 0에서 1칸 점프하면 된다. 

예시3) 거리가 5000일 때

: 2500에서 순간이동 하면된다.

: 2500는 ? 1250에서 순간이동 

: 1250은? 625에서 순간이동 

: 625는 ? 한칸 점프해서 624로 간 뒤 312에서 순간이동 

: 312는 ? 156에서 순간이동

: 156은? 78에서 순간이동

.....

: 순간이동은 거리가 짝수 일때만 할 수 있다. 순간이동을 하기 위해서는 홀수인 거리에서 한칸 점프(거리 -1 )해서 짝수로 만들어줘야한다.

✅풀이

#include <iostream>
using namespace std;

int solution(int n)
{
    int answer = 0;
    
    while(true)
	{ 
		if (n == 0)
			break;

		// 짝수면 > 나누기 2
		if (n % 2 == 0)
			n /= 2;

		// 홀수면 > 빼기 1
		else 
		{
			n -= 1;
			answer += 1;
		}
	}

    return answer;
}

https://github.com/kimYouChae/C-Programmers

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

[C++][프로그래머스][Lv2] 42842. 카펫

❗

노랑색의 가로가 w, 세로가 h일 때 

가능한 갈색의 타일 갯수는 ( 가로 + 2 ) x 2 + (세로 + 세로 ) 이다.

✅풀이방법

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int b, int y) {
    vector<int> answer;

	// yellow 기준으로 공약수 구하기

	for (int i = 1; i <= y; i++) 
	{
		// 나머지가 0이면 -> 나눠짐
		if (y % i == 0)
		{
			int tempWidth = y / i;
			int tempHeight = y / tempWidth;

			// 가능한 갈색의 갯수
			int broundTile = ( tempWidth + 2) * 2 + tempHeight * 2;

			// 가능한 갈색이랑 같으면 ?
			if(b == broundTile)
			{
				answer.push_back( tempWidth + 2);
				answer.push_back( tempHeight + 2);
				break;
			}
		}
	}
		
	
    return answer;
}

https://github.com/kimYouChae/C-Programmers

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

[C++][프로그래머스][Lv2] 12911. 다음 큰 숫자 

❗주의할 점 

: 10진수를 2진수로 바꾸는 방법을 알아야 풀 수 있는 문제였다.

: 얼마전에 비슷한 문제를 풀어서 푸는데 어려움은 없었다. 그리고 문제를 꼼꼼히 읽어야겠다는 생각을 했다....

✅ 사용한 함수

https://youcheachae.tistory.com/11

✅풀이방법 

#include <string>
#include <bitset>

using namespace std;

int solution(int _num) 
{
    int _idx = 1;
    int _answer = 0;

    // 기준이 되는 1의 갯수 
    int standartOneCnt = 0;
    // 2진수를 10진수로 변환 후, 문자열로 변환
    string numBinary = bitset<32>(_num).to_string();
    // 1로 시작하는 부분부터 끝까지 자르기
    string subNumBinary = numBinary.substr(numBinary.find('1'));

	// 기준이 되는 1의 갯수 구하기
    // algorithm 헤더의 count를 사용했으면 더 간편하게 가능함 
    for (int i = 0; i < subNumBinary.size(); i++)
    {
        if (subNumBinary[i] == '1')
            standartOneCnt++;
    }

    while (true)
    {
 	// 다음수 구하기 
        int _next = _num + _idx;

 	// 2진수 변환 후 1로 시작하는 부분~끝까지 자르기
        string _binary = bitset<32>(_next).to_string();
        string _subBinary = _binary.substr( _binary.find('1'));

	// 다음수의 1 구하기 
        int nextOneCount = 0;
        for (int i = 0; i < _subBinary.size(); i++)
        {
            if (_subBinary[i] == '1')
                nextOneCount++;	
        }

	// 문제조건 n과 n다음수를 2진수로 변환했을 때 1갯수가 같으면
        if (standartOneCnt == nextOneCount)
        {
            _answer = _next;
            break;
        }
        
        _idx++;
    }

    return _answer;
}

https://github.com/kimYouChae/C-Programmers

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

[C++][프로그래머스][Lv2] 70129. 이진 변환 반복하기 

❗주의할점 (1)

: 10진수를 2진수로 바꾸는 방법을 알아야 풀 수 있는 문제였다.

✅ #include <bitset>의 bitset< 생성할 bit 수 >(2진수로 변환할 수) 

#include <iostream>
#include <bitset>

using namespace std;

int main()
{
	int num = 150000;

	string str = bitset<32>(num).to_string();
	// 0000 0000 0000 0000 0000 0000 0000 0000 생성

	string temp = "";
	cout << str << endl;
      // 00000000000000100100100111110000 출력 

	for (int i = 0; i < str.size(); i += 4) {
		string temp = str.substr(i, 4);
		cout << temp << " ";
	}
      // 0000 0000 0000 0010 0100 1001 1111 0000 출력
    
}

: 문제에서 표기한 최댓값 150,000을 2진수로 변경해보았다.

: int 는 4바이트, 즉 32비트이다.  32비트안에 다 표현할 수 있다.

 ▶️32비트를 사용하면 문제조건에 맞게 2진수로 변경할 수 있다.

➕만약 bit수가 모자르면 어떻게 되는거지 ?

	int num = 150000;

	string str = bitset<6>(num).to_string();
        // 32비트 -> 6비트로 변경

: 32비트를 6비트로 바꾸어 출력해보았다.

: 오류가 뜰 꺼라 예상했지만, 생성한 비트수 만큼만 출력한다.

❗주의할점 (2)

: 10진수를 2진수로 변환 후, string으로 변환하는데 1이 나오기 전 0 은 0갯수를 카운트 할 때 들어가면 안된다.

	int num = 17;

	string str = bitset<32>(num).to_string();
	// 0000 0000 0000 0000 0000 0000 0000 0000 생성

	string temp = "";
	cout << str << endl;;

: 예를들어 17을 2진수로 바꾸었을 때

00000000000000000000000000010001 :  0개수 30개 , 1개수 2개 ❌

✅<string>헤더의 substr()과 find()

int num = 17;

string str = bitset<32>(num).to_string();
// 0000 0000 0000 0000 0000 0000 0000 0000 생성

string answer = str.substr(str.find('1'));
cout << answer << endl;

: 예를들어 17을 2진수로 바꾸었을 때

10001 : 0개수 3개, 1개수 2개 ⭕

: str.find(char c) : 문자열에서 char이 처음으로 나온 인덱스(type : int)를 반환한다.

: str.substr(int i) : 문자열에서 인덱스에서 시작해서, 맨 끝 까지 자른 string을 반환한다.

✅ <algorithm>헤더의 count(string의 시작 iterator , string의 끝 iterator , '찾을 문자 char ')

	int myCount = count(str.begin(), str.end(), '1');
	cout << myCount;

: 문자열안에서 해당 char 형 문자가 몇개 들어있는지, 갯수 (type : int)를 return 한다

✅ 풀이방법

#include <iostream>
using namespace std;
#include <string>
#include <algorithm>
#include <vector>
#include <bitset>

vector<int> solution(string str) {
    vector<int> answer;
    
    string temp = str;
    int wholeZero = 0;
    int progress = 0;
    while ( true )
    {
        if (temp == "1")
            break;

        progress++;
        int zero = count(temp.begin() , temp.end(), '0');
        int remain = temp.length() - zero;

        wholeZero += zero;

        // remian을 2진수로 (int형 변수를 2진수로 / int는 4바이트 32비트)
        string binaryStr = bitset<32>(remain).to_string();

        // binaryStr은 0000... 처럼 0 부터 시작할 수 도 있으니 자르기
        // string 의 find (1의 위치 찾음) , 시작 1부터 끝까지 자르기 
        string substrBinary = binaryStr.substr( binaryStr.find('1'));

        temp = substrBinary;
    }
    

    answer.push_back(progress);
    answer.push_back(wholeZero);
    return answer;
}

https://github.com/kimYouChae/C-Programmers