카라멜마끼아또

개인 공부를 위한 공간입니다
상업적 용도로 활용되지 않습니다

https://programmers.co.kr/learn/courses/30/lessons/42895

** 메모이제이션

이전에 계산한 값을 저장해놓고 계속 활용

v[0]~v[8]까지 N, NN, NNN 의 값을 먼저 저장

v[0]의 경우 N 한가지 경우밖에 없음

v[1]의 경우 NN, N+N, N*N, N-N, N/N 5가지 경우

NN

iterator ii:: v[0].begin()~v[0].end()

   it + iterator ji:: v[0].begin()~v[0].end()

   it * iterator ji:: v[0].begin()~v[0].end()

   it - iterator ji:: v[0].begin()~v[0].end()

   it / iterator ji:: v[0].begin()~v[0].end()

v[2]의 경우 NNN, NN+N, NN*N, NN-N, NN/N, N+N+N, N+N*N.......

v[1]를 계산하는 경우 v[0]의 값을 활용

v[2]를 계산하는 경우 v[1], v[0]의 값을 활용

v[3]을 계산하는 경우 v[2], v[1], v[0]의 값을 활용

v[k]를 계산하는 경우 v[i-1], v[i-2], v[i-3]...v[k-(j-1)]...v[0] 의 값을 활용

v[k]의 값 삽입이 끝난 후 

v[0]~v[k]까지의 값들을 한번 검색하여 number가 있다면 해당 k+1의 값이 answer로 출력(인덱스 0부터 시작하기 때문)

없다면 개수가 8개보다 큰 경우이기 때문에 -1 출력

int solution(int N, int number) {
	int answer = -1;
	vector<set<int>> v(8);
	int sum=0;
	// v[0]~v[8]까지 N, NN, NNN, NNNN... 값 저장
	for (int i = 0;i < 8;i++) {
		sum = 10 * sum +N;
		v[i].insert(sum);
    }
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < i; j++) {
			for (auto &ii : v[j]) {
				for (auto &ji : v[i-j-1]) {
					v[i].insert(ii + ji);
					v[i].insert(ii * ji);
					if(ii-ji>0)
						v[i].insert(ii - ji);
					if(ii/ji >0)
						v[i].insert(ii / ji);
				}
			}
		}
		if (v[i].find(number) != v[i].end()) 
			return i + 1;
	}
	return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/43165

풀이

재귀함수를 쓰는 DFS로 구현

using namespace std;

int dfs(vector<int> numbers, int target, int index, int num);

int solution(vector<int> numbers, int target) {
	int answer = 0;
	return dfs(numbers, target, 0, 0);
}


int dfs(vector<int> numbers, int target, int index, int num) {
	int size = numbers.size();
	if (index==size) {
		return num == target ? 1 : 0;
	}
	else {
		return dfs(numbers, target, index+1, num+numbers[index]) + dfs(numbers, target, index+1, num-numbers[index]);
	}
}

https://programmers.co.kr/learn/courses/30/lessons/1829

재귀함수를 사용한 DFS 알고리즘으로 구현

각 셀의 위 아래 오른쪽 왼쪽 4방향을 탐색하며 해당 셀이 현재 셀과 같은 색의 영역일 경우 다시 dfs에 돌입

하나의 영역을 탐색한 후 해당 영역의 셀의 개수를 반환하며 dfs 탈출

셀을 한칸한칸 탐색하며 탐색하지 않은 셀일 경우 다시 dfs를 불러 해당 영역을 모두 탐색

한 영역의 셀의 개수(cnt)들 중 가장 큰 값을 answer에 저장 (max함수)

풀이과정

1. main의 for문을 통해 모든 타일을 하나씩 탐색하며 dfs 함수 돌입

2. dfs 함수 내부에서 다시 for문을 통해 상, 하, 좌, 우 4개의 타일 탐색

3. 조건

인접 타일이 존재하면서 next_x >= 0 && next_y >= 0 && next_x < max_x && next_y < max_y

현재 타일과 인접 타일의 색상이 같고  pic[next_x][next_y]==pic[x][y]

그 인접 타일이 방문하지 않은 타일일 때 visit[next_x][next_y]!=1

카운트 (cnt) 증가 후 해당 타일의 좌표를 넣어 다시 dfs에 돌입

4. 하나의 섹션을 탐색하게 되면 섹션 크기의 최대값을 저장하는 변수 max_size_of_one_area 의 값과 비교하여

큰 값을 max_size_of_one_area 에 저장하고

총 섹션의 개수를 구하는 변수 number_of_area의 개수를 1 증가 후 dfs탈출

다시 main의 for문을 통해 다음 타일 탐색

----모든 타일 반복----

5. max_size_of_one_area, number_of_area 의 값을 결과로 리턴

vector<vector<int>> pic;
vector<vector<int>> visit;
vector<int> dx;
vector<int> dy;
int max_x;
int max_y;
int cnt;

int dfs(int x, int y) {
	visit[x][y] = 1;
	for (int i= 0; i < 4; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		if (next_x >= 0 && next_y >= 0 && next_x < max_x && next_y < max_y && pic[next_x][next_y]==pic[x][y] && visit[next_x][next_y]!=1) {		
			cnt++;
			dfs(next_x, next_y);
		}
	}
	return cnt;
}


vector<int> solution(int m, int n, vector<vector<int>> picture) {
	int number_of_area = 0;
	int max_size_of_one_area = 0;
	vector<int> answer(2);
	answer[0] = number_of_area;
	answer[1] = max_size_of_one_area;


	pic = picture;
	dx = { 0, 1, 0, -1};
	dy = { 1, 0, -1, 0 };
	max_x = m;
	max_y = n;
	vector<vector<int>> v(m, vector<int>(n, 0));
	visit = v;
	for (int i = 0; i < pic.size();i++) {

		for (int j = 0; j < pic[0].size(); j++) {

			if (visit[i][j] == 0 && pic[i][j]!=0) {
				cnt = 1;
				max_size_of_one_area = max(dfs(i, j), max_size_of_one_area);
				number_of_area++;
			}
		}
	}
	answer[0] = number_of_area;
	answer[1] = max_size_of_one_area;
	return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/64061

stack을이용하면 간단

인형을 뽑을 때마다 해당 인형의 값을 stack에 push

push하기 전에 조건문으로 stack.top()의 값이 지금 뽑은 인형과 같다면 pop()으로 터트리고 answer 2 증가(인형 두개가 터지니까)

뽑은 인형의 자리는 빈 자리 (0)으로 만듬

int solution(vector<vector<int>> board, vector<int> moves) {
	int answer = 0;
	stack<int> stack;
	for (int i = 0; i < moves.size(); i++) {
		for (int j = 0;j < board.size();j++) {
			if (board[j][moves[i]-1] != 0) {
				if (!stack.empty() && board[j][moves[i] - 1] == stack.top()) {
					stack.pop();
					answer+=2;
				}
				else 
					stack.push(board[j][moves[i] - 1]);
				board[j][moves[i] - 1] = 0;
				break;
			}
		}
	}
	return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/67256

하드코딩..

1 2 3

4 5 6

7 8 9

* 0 #

왼쪽, 오른쪽, 중앙값을 각 벡터에 넣어서 인덱스를 비교하는 것으로 거리 계산

** 왼손 혹은 오른손이 이미 2 5 8 0 위에 올라가 있을 때, 다시 2 5 8 0 을 누르기 위한 거리 계산을 빠뜨렸었음

int distance(int cur_pos, int num) {
	vector<int> vL = { 1, 4, 7, 10 };
	vector<int> vR = { 3, 6, 9, 12 };
	vector<int> vC = { 2, 5, 8, 0 };
	int index_pos, index_C;
	if (cur_pos == 1 || cur_pos == 4 || cur_pos == 7 || cur_pos == 10) {
		index_pos = find(vL.begin(), vL.end(), cur_pos) - vL.begin();
		index_C = find(vC.begin(), vC.end(), num) - vC.begin();
		return abs(index_C - index_pos);
	}
			
	else if (cur_pos == 3 || cur_pos == 6 || cur_pos == 9 || cur_pos == 12) {
		index_pos = find(vR.begin(), vR.end(), cur_pos) - vR.begin();
		index_C = find(vC.begin(), vC.end(), num) - vC.begin();
		return abs(index_C - index_pos);
	}
		
	else {
		index_pos = find(vC.begin(), vC.end(), cur_pos) - vC.begin();
		index_C = find(vC.begin(), vC.end(), num) - vC.begin();
		return abs(index_C - index_pos)-1;
	}
}

string solution(vector<int> numbers, string hand) {
	string answer = "";
	bool main_hand;
	int cur_pos_R = 12;
	int cur_pos_L = 10;

	if (hand == "right") 
		main_hand = true;
	else if (hand == "left")
		main_hand = false;

	cout << "main_hand: " << main_hand << endl;
	for (int i = 0; i < numbers.size(); i++) {
		cout << "numbers["<<i<< "]: " << numbers[i]<< endl;
		if (numbers[i] == 1 || numbers[i]==4 || numbers[i]==7) {
			cur_pos_L = numbers[i];
			answer.push_back('L');
		}
		else if (numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9) {
			cur_pos_R = numbers[i];
			answer.push_back('R');
		}
		else {
			int dis_R = distance(cur_pos_R, numbers[i]);
			int dis_L = distance(cur_pos_L, numbers[i]);

			if (dis_R < dis_L) {
				cur_pos_R = numbers[i];
				answer.push_back('R');
			}
			else if (dis_R > dis_L) {
				cur_pos_L = numbers[i];
				answer.push_back('L');
			}
			else {
				if (hand == "right") {
					cur_pos_R = numbers[i];
					answer.push_back('R');
				}
				else {
					cur_pos_L = numbers[i];
					answer.push_back('L');
				}
			}
		}
	}
	return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/81301

하드코딩..

단순하게 for문으로 문자열 검색하면서 one은 1, two는 2..... zero는 0으로 치환 후 string s 변수에 저장

stoi로 형변환 후 출력

int solution(string s) {
	int answer = 0;
	string result="";
	for (int i = 0; i < s.size();i++) {
		if (s[i] == 'o') {
			result.push_back('1');
			i += 2;
		}
		else if (s[i] == 't') {
			if (s[i+1] == 'w') {
				result.push_back('2');
				i += 2;
			}
				
			else {
				result.push_back('3');
				i += 4;
			}
		}
		else if (s[i] == 'f') {
			if (s[i+1] == 'o')
				result.push_back('4');
			else 
				result.push_back('5');
			i += 3;
		}
		else if (s[i] == 's') {
			if (s[i+1] == 'i') {
				result.push_back('6');
				i += 2;
			}

			else {
				result.push_back('7');
				i += 4;
			}
		}
		else if (s[i] == 'e') {
			result.push_back('8');
			i += 4;
		}
		else if (s[i] == 'n') {
			result.push_back('9');
			i += 3;
		}
		else if (s[i] == 'z') {
			result.push_back('0');
			i += 3;
		}
		else {
			result.push_back(s[i]);
		}

	}
	answer = stoi(result);
	return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/17676

int solution(vector<string> lines) {
	int answer = 0;
	vector<string> temp = lines;
	vector<int> start;
	vector<int> end;



	for (int i = 0; i < temp.size();i++) {
		int h, m, s, ms;
		float duration;
		temp[i].pop_back();
		h = stoi(lines[i].substr(11, 2)) * 3600 * 1000;
		m = stoi(lines[i].substr(14, 2)) * 60 * 1000;
		s = stoi(lines[i].substr(17, 2)) * 1000;
		ms = stoi(lines[i].substr(20, 3));
		duration = stof(lines[i].substr(24, 5)) * 1000;
		start.push_back(h + m + s + ms - duration + 1);
		end.push_back(h + m + s + ms);
	}

	for (int i = 0; i < lines.size();i++) {
		int end_t = end[i] + 1000;
		int cnt = 1;
		for (int j = i + 1; j < lines.size();j++) {
			int current_t = start[j];
			if (end_t > current_t) {
				cnt++;
			}
		}
		answer = max(answer, cnt);

	}
	return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/42888

id_name 에 key로 id, value로 name 정보 저장(닉네임 정보)

Stringstream으로 record의 문자열을 공백 기준으로 구분

첫 번째 : state

두 번째 : id

세 번째 : name

state:: Enter

id + " 들어왔습니다." 

state:: Change

id 변경

state:: Leave

id +" 나갔습니다."

vector<string> solution(vector<string> record) {
	vector<string> answer;
	unordered_map<string, string> id_name;
	vector<pair<string,string>> result;

	for (int i = 0; i < record.size();i++) {
		string first, second, third;
		stringstream sstream;
		sstream.str(record[i]);
		sstream >> first >> second >> third;
		
		if (first == "Enter") {
			id_name[second] = third;
			result.push_back(make_pair(second, "들어왔습니다."));

		}
		else if(first == "Leave")
			result.push_back(make_pair(second, "나갔습니다."));
		else if(first =="Change")
			id_name[second] = third;
	}
	for (int i = 0; i < result.size();i++) {
		answer.push_back(id_name[result[i].first] + "님이 " + result[i].second);
	}
	return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/60057

* 문제를 이해하는것이 가장 중요

* 여러 테스트 케이스 활용

**** 테스트케이스 "xxxxxxxxxxyyy" 의 경우 압축이 되면 10x3y 로 x가 10개, 두자리 수로 압축되기 때문에 해당 조건 꼭 넣어줘야 됨!!

int comp(string s, int n) {
	string temp;
	int times=s.size()/n;
	int size = s.size();
	int flag = 0;
	int cnt = 0;

	temp = s.substr(0, n);

	for (int i = 0; i < times; i++) {
		string next = s.substr((i+1)*n, n);
		if (temp.compare(next) == 0) {
			size -= n;
			flag++;
		}
		else if (flag != 0 && flag<9) {
			size++;
			flag = 0;			
		}
		else if (flag != 0 && flag>=9) {
			size++;
			size++;
			flag = 0;
		}
		
		temp = next;
	}
	return size;
}
int solution(string s) {
	int answer = s.size();
	string temp=s;
	
	
	for (int i = 1; i <= s.size(); i++) {
		answer = min(answer, comp(temp, i));
	}
	return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/72410

아스키 값 활용하여 단계별로 수행

new_id가 빈 문자열일 경우 5단계, 7단계만 수행하기 때문에 무조건 aaa 반환

각 단계별로 변환된 id 값을 tmp 에 저장

모든 단계를 마친 후 answer에 tmp의 값을 저장

while 문을 사용하여 변환 횟수를 탐지(cnt)

while문 한 번 돌 때 변환이 한번도 일어나지 않았다면 변환 완료된 경우이므로 while문 탈출 후 출력

1. 대문자의 경우 아스키 값에 32를 더한 후 char로 형변환화여 소문자로 출력

2. 아스키값 범위를 사용해서 허용된 문자가 아니면 삭제하여 저장

3, 4. 연속된 마침표를 검사하여 하나의 마침표만 출력. 해당 마침표가 시작, 끝일 경우 넘어감

5. 빈 문자열일 경우 a 저장

6. 최초 15개의 문자만 저장

7. 길이 2 이하인 id에 끝 글자를 계속 더해서 길이 3을 만듬

string solution(string new_id) {
	string answer = new_id;
	string tmp;
	int cnt=1;

	if (new_id.size() == 0) {
		answer.push_back('aaa');
		return answer;
	}


	while (cnt) {
		cnt = 0;
		// 1
		for (int i = 0; i < answer.size();i++) {
			int asc = answer[i];
			if (asc <= 90 && asc >= 65) {
				tmp.push_back((char)asc + 32);
				cnt++;
			}
			else
				tmp.push_back((char)asc);
		}
		answer.clear();
		answer = tmp;
		tmp.clear();

		// 2
		for (int i = 0; i < answer.size();i++) {
			int asc = answer[i];
			if (asc != 46 && asc != 45 && asc != 95 && (asc < 48 || asc>57) && (asc < 97 || asc>122)) {
				cnt++;
				continue;
			}
			else
				tmp.push_back((char)asc);
		}
		answer.clear();
		answer = tmp;
		tmp.clear();

		// 3+4
		for (int i = 0; i < answer.size();i++) {
			int asc = answer[i];
			int asc2 = answer[i + 1];
			if (asc == 46 && asc2 == 46) {
				cnt++;
				continue;
			}
			else {
				if (asc == 46 && (tmp.empty() || answer[i + 1] == NULL)) {
					cnt++;
					continue;
				}
				tmp.push_back((char)asc);
			}
		}
		answer.clear();
		answer = tmp;
		tmp.clear();


		// 5
		if (answer.size() == 0) {
			cnt++;
			answer.push_back('a');
		}


		// 6
		if (answer.size() >= 16) {
			while (answer.size() > 15) {
				cnt++;
				answer.pop_back();
			}
		}

		// 7
		if (answer.size() <= 2) {
			while (answer.size() <= 2) {
				cnt++;
				answer.push_back(answer[answer.size() - 1]);
			}

		}
	}
	return answer;
}