프로그래밍

https://leetcode.com/problems/count-good-nodes-in-binary-tree/

[풀이]

1. 재귀를 이용해서 이진트리의 모든 노드들을 순회한다.

2. 파라미터 v는 현재 node의 부모 node들의 value 중에 가장 큰 value를 의미한다.

3. 현재 노드의 value가 v보다 크면 return 값에 1을 더해 주어 결과값에 추가될 수 있도록 한다.

4. root는 무조건 추가되어야 하므로 main에서 -100000을 v에 넣어준다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

	int search(TreeNode* node, int v) {

		if (node == nullptr) return 0;
 
		int ret = 0;
		int cur_max = v;
		if (node->val >= v) {
			cur_max = node->val;
			ret++;
		}
		ret += search(node->left,  cur_max);
		ret += search(node->right, cur_max);

		return ret;
	}

	int goodNodes(TreeNode* root) {
		return search(root, -100000);
	}
};

https://github.com/has2/Algorithm/blob/master/leetcode/1448.cpp

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

[풀이] 재귀,구현,Stack

문제에 써있는 대로 구현하면 된다.

1. 균형잡힌 괄호 문자열 찾기 int getBalance(string& s)

  여는 괄호와 닫는 괄호의 갯수가 같아지는 순간의 index를 반환

2. 올바른 문자열 체크 bool isRight(string& s)

  stack을 이용하였다. 여는 괄호의 경우 무조건 push, 닫는 괄호인 경우에

  stack이 비어있으면 올바른 괄호 문자열이 아니므로 false 리턴

위의 두 함수를 이용해서 재귀적으로 solution 함수를 채워주면 된다.

#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
string p = "()";
int getBalance(string& s) {
	int ret = 0;
	int l=0, r=0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '(') l++;
		else r++;
		if (l == r) {
			ret = i+1;
			break;
		}
	}
	return ret;
}

bool isRight(string& s) {
	stack<int> st;

	for (int i = 0; i < s.size(); i++) {
		char c = s[i];
		if (c == '(') {
			st.push(c);
		}
		else {
			if (st.empty()) {
				return false;
			}
			else {
				st.pop();
			}
		}

	}
	return true;
}
string rev(string& s) {
	string ret = "";
	for (int i = 1;i<s.size()-1;i++) {
		ret.push_back(s[i] == ')' ? '(' : ')');
	}
	return ret;
}

string solution(string p) {
	
	if (p == "") return p;
	string ret;

	int sz = getBalance(p);
	string w = p.substr(0, sz);
	string u = p.substr(sz, p.size() - sz);

	string k = solution(u);
	if (isRight(w)) {
		ret = w + k;
	}
	else {
		ret = "("+k+")";
		ret += rev(w);
	}
	return ret;
}

https://github.com/has2/Algorithm/blob/master/programmers/level2/%EA%B4%84%ED%98%B8%20%EB%B3%80%ED%99%98.cpp

https://leetcode.com/problems/subrectangle-queries/

#include <vector>
#include <algorithm>
using namespace std;
class SubrectangleQueries {
public:
	vector<vector<int>> rec;
	SubrectangleQueries(vector<vector<int>>& rectangle) {
		rec = rectangle;
	}

	void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
		for (int i = row1; i <= row2; i++) {
			fill(rec[i].begin()+col1, rec[i].begin()+col2+1, newValue);
		}
	}

	int getValue(int row, int col) {
		return rec[row][col];
	}
};

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

[풀이]

DFS

#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int dy[4] = { 1,-1,0,0 };
int dx[4] = { 0,0,1,-1 };
int M, N;
bool visit[101][101];

int dfs(vector<vector<int>>& picture, int y, int x) {
	
	visit[y][x] = 1;

	int ret = 1;
	for (int i = 0; i < 4; i++) {
		int ty = y + dy[i];
		int tx = x + dx[i];
		
		if (ty < 0 || tx < 0 || ty >= M || tx >= N || visit[ty][tx]
			|| picture[ty][tx] != picture[y][x]) continue;

		ret += dfs(picture, ty, tx);
	}
	return ret;
}

vector<int> solution(int m, int n, vector<vector<int>> picture) {
	int number_of_area = 0;
	int max_size_of_one_area = 0;
	M = picture.size();
	N = picture[0].size();

	memset(visit, 0, sizeof(visit));

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (picture[i][j] == 0 || visit[i][j]) continue;
			number_of_area++;
			max_size_of_one_area = max(max_size_of_one_area, dfs(picture, i, j));
		}
	}


	vector<int> answer(2);
	answer[0] = number_of_area;
	answer[1] = max_size_of_one_area;
	return answer;
}

https://github.com/has2/Algorithm/blob/master/programmers/level2/%EC%B9%B4%EC%B9%B4%EC%98%A4%20%ED%94%84%EB%A0%8C%EC%A6%88%20%EC%BB%AC%EB%9F%AC%EB%A7%81%EB%B6%81.cpp

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/60057

[풀이과정]

1. 문자열 길이가 n인 경우 1~n/2으로 잘랐을 경우를 모두 구한다. (n/2를 넘게 자르는 것은 불가능)

2. 길이 len으로 자른 경우 길이가 len인 substring을 한개씩 비교하면서 앞의 것과 같으면 압축 가능한 개수를 저장하는 cnt를 1 더해준다.

3. 다른 문자열이 나오면 cnt의 길이 + len만큼을 ret에 더해준다.

 (cnt를 string으로 변환 후 size 구함, cnt가 1인 경우 더해주지 않음)

4. 다음 index (i+len)이 s의 길이를 초과하는 경우 더 이상 압축이 불가능 하므로 남아있는 것을 더해준다.

   (s2.size()만큼 더해주는 이유는 제일 마지막 부분 문자열은 len보다 작을수도 있기 때문에)

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

int sol(string& s, int len) {

	int ret = 0;

	int cnt = 1;
	for (int i = len; i < s.size() ; i += len) {
		string s1 = s.substr(i-len, len);
		string s2 = s.substr(i, len);
		//cout << s1 << "," << s2 << endl;
		if (s1 == s2) {
			cnt++;
		}
		else {
			ret += len;
			if (cnt != 1) ret += to_string(cnt).size();
			cnt = 1;
		}
		if (i + len >= s.size()) {
			ret += s2.size();
			if (cnt != 1) ret += to_string(cnt).size();
		}
		//cout << ret << endl;

	}
	return ret;
}

int solution(string s) {
	if (s.size() == 1) return 1;

	int answer = 10000;

	for (int i = 1; i <= s.size() / 2; i++) {
		answer = min(answer,sol(s, i));
	}

	return answer;
}

https://github.com/has2/Algorithm/blob/master/programmers/level2/%EB%AC%B8%EC%9E%90%EC%97%B4%20%EC%95%95%EC%B6%95.cpp

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42583

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
	int answer = 0;
	queue<pair<int,int>> q;

	int cnt = truck_weights.size();
	int cur_i = 0;
	int cur_w = 0;
	int time = 0;

	while (1) {

		if (cur_i < cnt && cur_w + truck_weights[cur_i] <= weight) {

			int qsize = q.size();
			while (qsize--) {

				auto truck = q.front();
				q.pop();
				if (truck.second != bridge_length) {
					q.push(make_pair(truck.first, truck.second + 1));
				}
				else {
					cur_w -= truck_weights[truck.first];
				}
			}
			
			cur_w += truck_weights[cur_i];
			q.push(make_pair(cur_i++, 1));
			time++;
		}
		else if (!q.empty()) {

			auto truck = q.front();
			q.pop();

			cur_w -= truck_weights[truck.first];

			int offset = bridge_length - truck.second+1;
			int qsize = q.size();
			while (qsize--) {
				truck = q.front();
				q.pop();
				q.push(make_pair(truck.first, truck.second + offset));
			}

			if (cur_i < cnt && cur_w + truck_weights[cur_i] <= weight) {
				cur_w += truck_weights[cur_i];
				q.push(make_pair(cur_i++, 1));
			}

			time += offset;
		}
		else {
			answer = time;
			break;
		}
		//printf("time : %d\n", time);
	}
	
	return answer;
}

int main() {

	int bridge = 2;
	int wi = 10;
	vector<int> a = { 7,4,5,6 };

	//int bridge = 100;
	//int wi = 100;
	//vector<int> a = { 10 };

	//int bridge = 1;
	//int wi = 6;
	//vector<int> a = { 6,6};

	printf("%d", solution(bridge, wi, a));

}

소스코드 : https://github.com/has2/Algorithm/blob/master/programmers/level2/%EB%A9%80%EC%A9%A1%ED%95%9C%20%EC%82%AC%EA%B0%81%ED%98%95.cpp