WantAirpod

www.welcomekakao.com/learn/courses/30/lessons/42897

문제설명

간단히 인접하지 않은 두 집을 털어 max 값을 구해주는 문제이다.

점화식

• 첫번째 집부터 터는 경우 = 마지막 집 선택의 경우
• 두번째 집부터 터는 경우 = 마지막 집 선택 X 경우 

현재 도둑질하려는 집의 돈 +  max ( (현재집 -2)집의 돈, (현재집 -1)집의 돈 )

C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int dp[1000000] = { 0, };
int solution(vector<int> money)
{
	vector <long> one;
	vector <long> two;
	int msize = money.size();
	one.resize(msize, money[0]);
	two.resize(msize, money[1]);
	two[0] = 0;
	for (int i = 2; i <= msize - 2; i++)
		one[i] = max(one[i - 2] + money[i], one[i - 1]);

	for (int i = 2; i <= msize - 1; i++)
		two[i] = max(two[i - 2] + money[i], two[i - 1]);

	return max(one[msize - 2], two[msize - 1]);
}

int main()
{
	solution({ 1, 2, 3, 1, 2, 3 });
	return 0;
}

Java

import java.util.*;
public class 프로그래머스Lv4_도둑질_Dp {
	static int solution(int [] money)
	{
		//ArrayList<Integer> one;
		//ArrayList<Integer> two;
		int msize =money.length;
		int [] one  = new int [msize+1];
		int [] two  = new int [msize+1];
		
		one[0] = money[0];
		one[1] = money[0];
		one[2] = money[0];
		
		two[0] = money[1];
		two[1] = money[1];
		two[2] = money[1];
		
		//one.resize(msize, money[0]);
		//two.resize(msize, money[1]);
		//two[0] = 0;
		for (int i = 2; i <= msize - 2; i++)
			one[i] = Math.max(one[i - 2] + money[i], one[i - 1]);

		for (int i = 2; i <= msize - 1; i++)
			two[i] = Math.max(two[i - 2] + money[i], two[i - 1]);

		return Math.max(one[msize - 2], two[msize - 1]);
	}

	public static void main(String[] args) 
	{
		// TODO Auto-generated method stub
		int [] num= {1,2,3,1,2,3};
		System.out.println(solution(num));
	}

}

GetLine() 함수 

문제점 1) 가나다 라마바 사아자 라고 입력이 되었다고 치면 cin 또는 scanf로 입력 받을 시 가나다에서 끊기고 만다.

해결 : getline 함수를 이용

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int main()
{
 
	char name[20];
	char dessert[20];
	
	cout << "name" << endl;
	cin.getline(name, 20);  //20글자 까지 받을 수 있다.
	cout << "dessert" << endl;
	cin.getline(dessert, 20);

	cout << "good" << dessert;
	cout << "dessert " << name << "sir " << endl;

	return 0;
}

문제점 2) 위의 코드로 입력 받을 시 한글이 무조건 깨진다.

이유 : ASCIII (거의 100%이거 때문임) ->

해결 : 멀티바이트 문자 집합 이용 (거의 100% 이게 해결법임)

단, 해당 문자 집합을 이용하면 그에 맞는 함수도 가져가야한다.

한글을 출력하기 위해서는 로케일 설정을 한국으로 바꿔줘여한다.

전체 로케일 설정

• locale::global(locale("kor"));

부분 로케일 설정

• wcout.imbue(locale("kor"));

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int main()
{
	wcout.imbue(locale("kor"));//한국으로 지역설정
	wcin.imbue(locale("kor")); 
	wchar_t name[20];
	wchar_t dessert[20];
	
	wstring str1;
	wstring str2; 

	wcout << "name" << endl;
	wcin.getline(name, 20);
	wcout << "dessert" << endl;
	wcin.getline(dessert, 20);

 
	wcout << "good" << dessert;
	wcout << "dessert " << name << "sir " << endl;


	return 0;
}

만약 wchar_t가 아닌 string에 담고 싶다면 string 대신 wstring을 사용한다.

코드 

	wcout.imbue(locale("kor"));//한국으로 지역설정
	wcin.imbue(locale("kor"));
    
	wstring str1;
	getline(wcin, str1);

lower_bound란

이진탐색(Binary Search)기반의 탐색 방법. (배열 또는 리스트가 정렬 되어야 있어야함.)

 : 찾고자 하는 값 이상의 값이 처음 나타나는 "위치" 

	int arr[10] = {1,2,4,5,6,6,7,7,7,9 };
	//lower_bound : 정수 값 찾음
	cout << "lower_bound(6) : " << lower_bound(arr, arr + 10, 6) - arr  << endl; //4
	cout << "lower_bound(7) : " << lower_bound(arr, arr + 10, 7) - arr  << endl; //6
	cout << "lower_bound(8) : " << lower_bound(arr, arr + 10, 8) - arr  << endl; //9
	cout << "lower_bound(9) : " << lower_bound(arr, arr + 10, 9) - arr  << endl; //9

단, 만약 못찾으면 찾고자 하는 값 배열의 마지막 위치를 반환한다.

upper_bound

lower_bound와 마찬가지로 이진탐색기반의 탐색법 이진탐색(Binary Search)기반이므로 배열이나 리스트가 오름차순으로 정렬 되어야한다.

 : 찾고자 하는 값 초과하는 값이 처음 나타나는 "위치"

	cout << "upper_bound(6) : " << upper_bound(arr, arr + 10, 6) - arr  << endl; //6
	cout << "upper_bound(7) : " << upper_bound(arr, arr + 10, 7) - arr  << endl; //9
	cout << "upper_bound(8) : " << upper_bound(arr, arr + 10, 8) - arr  << endl; //9
	cout << "upper_bound(9) : " << upper_bound(arr, arr + 10, 9) - arr  << endl; //10

단, 만약 못찾으면 찾고자 하는 값 배열의 마지막 위치를 반환한다.

문제

문제설명

hit에서 cog를 가는 방법의 갯를 리턴

시행착오

처음에 DFS로 풀려고 시도했는데 words를 탐색할때 앞으로 갔다가 뒤로 갔다가 하니깐 visit 처리가 꼬이면서 결국 gg

풀면서도 bfs로 풀면 쉽겠다 생각이 들어서 40분동안 dfs로 풀다가 결국 bfs로 넘어가서 쉽게 품...

하지만, bfs에서 계속 2,3번이 안나옴 알고보니 꼭 words가 세글자가 아닌 10글자까지 가능한 것... 문제 잘 읽자..

문제풀이

1) begin값에서 변환가능한 모든 경우의 수를 queue에 넣음 

2) bfs를 돌리며 target이 나오는 순간 모든 함수 종료

3) 트리구조를 떠올리며 자식 노드로 이동 할때 +1을 해주기 위해 queue를 페어로 구현하였고 두번째 값에 노드 번째를 나타냄.

난이도

★★★☆☆

dfs 하면서 오기 생겨서 테스트케이스 많이 생성하게 됨... dfs로 다시 구현 예정..

코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
bool visit[50] = { false, };
 
bool flag = false;
int bfs(string begin, vector<string> words, int num, string target)
{
	int answer = 100;
	queue<pair<string, int>> q;
	q.push({ begin,0 });
	int sizeQueue = 0; 
	int ansNum = 0;
	while(!q.empty())
	{ 
		if (flag == true)
			break; 
		string begin = q.front().first;
		int ansNum = q.front().second;
		q.pop();
		ansNum++;  
		for (int w = 0; w < words.size(); w++)
		{
			int cnt = 0;
			for (int i = 0; i < begin.length(); i++)
			{
				if (begin[i] == words[w][i])
				{
					cnt++;
				}
			} 
			if (cnt == begin.size()-1 && !visit[w])
			{
				if (words[w] == target)
				{
					flag = true; 
					answer = ansNum;
					break;
				}
				visit[w] = true;
				q.push({ words[w],ansNum });
			}
		} 
		sizeQueue = q.size(); 
	}

	return answer;


}

int solution(string begin, string target, vector<string> words)
{
	int answer = 100;
	int in = 100;
	 
	in = bfs(begin, words, 0, target);
	answer = min(in, answer);
	in = 0;
	 
	if (answer == 100)
		answer = 0;
	return answer;
}

int main()
{
	cout << solution("hit", "cog", { "hot", "dot", "dog", "lot", "log","cog" }) << endl;// hot -> dot -> dog -> log -> cog 
 	//cout << solution("hit", "hhh", { "hhh", "hht" }) << endl; //2
	//cout << solution("zzz", "zzz", { "zzz" }) << endl;
	//cout << solution("hit", "zzz", { "zzz" }) << endl;
	//cout << solution("hit", "zzz", { "zzz", "zyz", "xzz", "xyz", "hyt", "hyz", "xiz", "hiz" }) << endl;// 4 :  hyt -> xiz -> xzz -> zzz //4번



}

문제

입출력 예시

풀이방법

1) 마스킹된 제재사용자 아이디로 가능한 유저 아이디를 체크한다.

2) 체크한 아이디들의 경우의 수를 따져준다. 

  2)-1 각각의 유저 아이디는 순서가 바뀐것은 하나로 취급한다.

3) 각 유저아이디의 조합의 경우를 count 해준다.

1) 이중포문으로 가능한 경우의 유저 아이디의 index를 추출하여 벡터에 담는다.

2) 체크한 아이디의 경우의 수를 따져주기 위해서 set 자료 구조를 이용 하였다. 

ex) 0123 = 0132가 같은 경우의 수 이기 때문이다. 단 set에 넣을 때는 0123과 0132일 떄 visit배열에 체크를 하였고 0부터 차례 대로 visit여부에 따라서 string으로 형변환하여 0132는 0123꼴로 나타내줬다 그래야만 set에 들어갈때 중복제거가 가능하기 때문이다.

3) 상기 set에 조합을 넣은 이유는 결론적으로 set에 들어간 크기가 전체 조합의 경우의 수와 같다는 것을 의미하기 때문

난이도

★★★☆☆

dfs를 구현하고 set에 어떻게 넣을지 고민을 좀 오래했음.. visit배열을 순서대로 추출하여 적재하는 방식은 구글에 도움을 받음.. 항상 풀고 나면 덜 어려워 보임 (다시 풀어볼 만함)

코드

#include <iostream>
#include <vector>
#include <set>
#include <string>
using namespace std;
bool visit[50] = { false, };

vector<int> v[10];
 
set<string> s;

void  dfs(int num, int N) 
{
	if (num == N) 
	{
		string tmepStr = "";
		for (int i = 0; i < 10; i++)
			if (visit[i] == 1)
			{
				tmepStr += to_string(i);
			}
		s.insert(tmepStr);
		return;
	}

	for (int j = 0; j < v[num].size(); j++) 
	{
		int cur = v[num][j];
		if (visit[cur] == 1) continue;
		visit[cur] = 1;
		dfs(num + 1, N);
		visit[cur] = 0;
	}
 
} 

int solution(vector<string> user_id, vector<string> banned_id)
{
	int answer = 0;
	for (int i = 0; i < banned_id.size(); i++)
	{
		for (int j = 0; j < user_id.size(); j++)
		{

			int cnt = 0;
			int starcnt = 0;
			if (banned_id[i].length() != user_id[j].length())
				continue;
			for (int w = 0; w < banned_id[i].length(); w++)
			{
			
				if (banned_id[i][w] == '*')
				{
					starcnt++;
					continue;
				}
				if (banned_id[i][w] != user_id[j][w])
				{
					break;
				}
				else if( banned_id[i][w] == user_id[j][w])
				{
					cnt++;
				}
			}
			if (user_id[j].length() - starcnt == cnt)
			{
				v[i].push_back(j);
				//visit[j] = true;
			}
		}
	}
	 dfs(0, banned_id.size());
	 answer = s.size();
	return answer;
}
int main()
{
	//solution({ "frodo","fradi","crodo","abc123","frodoc" }, { "fr*d*","abc1**" });
	solution({ "frodo","fradi","crodo","abc123","frodoc" }, { "fr*d*","*rodo","******","******"});
	return 0;
}

문제

TC

자료구조 흐름

SOL 코드

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#define PP pair<int,int>

using namespace std;

bool cmp(PP a, PP b)
{
   if (a.second > b.second)
      return true;
   else if (a.second == b.second)
   {
      if (a.first < b.first)
         return true;
      else
         return false;
   }
   else
      return false;
}

bool cmp2(pair<string, vector<pair<int, int>>> a, pair<string, vector<pair<int, int>>> b)
{
   if (a.second[0].second > b.second[0].second)
      return true;
   else
      return false;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
   vector<int> answer;
   map<string, vector<pair<int,int>>> m;
   for (int i = 0; i < genres.size(); i++)
   {
      if (m.find(genres[i]) == m.end())
      {
         vector<pair<int, int>> v;
         v.push_back(make_pair(i, plays[i]));
         m.insert(make_pair(genres[i], v));
      }
      else
         m[genres[i]].push_back(make_pair(i, plays[i]));
   }

   vector<pair<string, vector<pair<int, int>>>> v;
   v.assign(m.begin(), m.end());
   
   for (int i = 0; i < v.size(); i++)
   {
      int cnt = 0;
      for (int j = 0; j < v[i].second.size(); j++)
         cnt += v[i].second[j].second;
      v[i].second.push_back(make_pair(cnt, cnt));
   }
   
   for (int i = 0; i < v.size(); i++)
      sort(v[i].second.begin(), v[i].second.end(), cmp);

   sort(v.begin(), v.end(), cmp2);

   for (int i = 0; i < v.size(); i++)
   {
      for (int j = 0; j < v[i].second.size(); j++)
      {
         if (v[i].second[j].first == v[i].second[j].second)
            continue;
         answer.push_back(v[i].second[j].first);
         if (j == 2)
            break;
      }
   }

   return answer;
}

int main()
{
   solution({ "classic", "pop", "classic", "classic", "pop", "AG" }, { 500, 600, 150, 800, 2500, 300 });
}

개념

조합(Combination) : 순서 바뀜 허용 안함, 중복 허용 안함, nCr = n! / r! * (n-r)!

순열(Permutation) : 순서 바뀜 허용,         중복 허용 안함, nPr = nCr x r!

*순서 바뀜

ex) 1 1 2 & 1 2 1 --> Per 허용, Com 허용X

ex) {1,2,3} 

조합(3C2): {1,2}, {2,3}, {3,1}

순열(3PC) : {1,2}, {2,1}, {2,3}, {3,2}, {3,1}, {1,3}

조합(3C2) : {1,2,3}

순열(3PC) : 3개의 우너소로 조합 가능한 모든 구성 : 3P3 (nPn = n!) 

{1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1} 

순열(Permutation)는 w=0

조합(Combination)은 w=num

단, 중복을 허용할 시 visit배열을 없애 준다.!!

코드

void Permutition(int ctttt, int num )
{
	if(ctttt==3)
	{
		vector <int > ans;		
		for(int i = 0 ; i < vvvvv_.size() ; i++)
		{
			cout <<" " <<vvvvv_[i]   ; 
		}
		cout<< endl;
		return ;
	}

//permu는 w=0 
	for(int w= 0 ; w<5 ;w ++)
	{
		if(!vii[w])
		{	vii[w]=true;
		vvvvv_.push_back(ex_Num[w]); //0	
		Permutition(ctttt+1,w);
		vvvvv_.pop_back(); 
		vii[w] =false;
		} 
	}

}
void Combination(int ctttt, int num )
{
	if(ctttt==3)
	{
		vector <int > ans;		
		for(int i = 0 ; i < vvvvv_.size() ; i++)
		{
			cout <<" " <<vvvvv_[i]   ; 
		}
		cout<< endl;
		return ;
	}

//combi는 w=num
	for(int w= num ; w<5 ;w ++)
	{
		if(!vii[w])
		{	vii[w]=true;
		vvvvv_.push_back(ex_Num[w]); //0	
		Combination(ctttt+1,w);
		vvvvv_.pop_back(); 
		vii[w] =false;
		} 
	}

}

문제

문제해석

• 4개이상 같은 문자이면 터짐
• 터진 자리에 .으로 채워짐

입출력

풀이

• 12*6 이라는 배열 크기보고 터지진 않겠다라는 생각을함
• 탐색은 세로로 하다가 처음 .이 아닌 문자를 만났을때 BFS를 수행하는게 좋을 것 같다.
• BFS진행 시 cnt값을 주어 4이상일 경우에만 문자->"." 으로 바꿔줘야 겠다고 생각함.

난이도

★★★☆☆

다시 풀어볼만함 약 45분 걸림

SOL코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>

using namespace std;

struct cmp
{
	bool operator() (pair<int, int> a, pair<int, int> b)
	{
		if (a.first < b.first)
			return true;
		else if (a.first == b.first)
		{
			if (a.second > b.second)
				return true;
			else
				return false;
		}
		else
			return false;
	}
};

int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
char ar[12][6];
int ans;
vector<char> v[6];
bool flag = false;
set<pair<int, int>, cmp> res;

void input()
{
	for (int i = 0; i < 12; i++)
	{
		for (int j = 0; j < 6; j++)
			cin >> ar[i][j];
	}

	for (int i = 0; i < 6; i++)
	{
		for (int j = 11; j >= 0; j--)
			v[i].push_back(ar[j][i]);
	}
}

void break_puyo(char c, int  i, int j)
{
	queue<pair<int, int>> q;
	vector<pair<int, int>> bre_pu;
	bool vi[6][12] = { false, };
	q.push(make_pair(i, j));
	vi[i][j] = true;

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		bre_pu.push_back(make_pair(x, y));

		for (int w = 0; w < 4; w++)
		{
			int nx = x + dx[w];
			int ny = y + dy[w];
			if (nx < 0 || nx >= 6 || ny < 0 || ny >= 12)
				continue;
			if (!vi[nx][ny] && v[nx][ny] == c)
			{
				vi[nx][ny] = true;
				q.push(make_pair(nx, ny));
			}
		}
	}

	if (bre_pu.size() >= 4)
	{
		for (int w = 0; w < bre_pu.size(); w++)
			res.insert(bre_pu[w]);
		flag = true;
	}
}

void solve()
{
	while (true)
	{
		if (res.size() > 0)
			res.clear();
		flag = false;
		for (int i = 0; i < 6; i++)
		{
			for (int j = 0; j < 12; j++)
			{
				if (v[i][j] == '.')
					break;
				break_puyo(v[i][j], i, j);
			}
		}
		if (!flag)
			break;

		ans++;
		for (set<pair<int, int>, cmp>::iterator iter = res.begin(); iter != res.end(); iter++)
		{
			pair<int, int> s = *iter;
			int x = s.first;
			int y = s.second;
			v[x].erase(v[x].begin() + y);
			v[x].push_back('.');
		}
	}
}

int main()
{
	input();
	solve();
	cout << ans << endl;
	return 0;
}