프로그래밍

https://www.acmicpc.net/problem/2632

[풀이] 완전탐색,부분합

1. n,m 제한이 1000이므로 모든 연속된 구간의 합 sum을 계산한다.

2. sum이 어떤 구간에 있는지는 중요하지 않고 몇개나 나올 수 있는지가 중요하므로

   Acnt,Bcnt 배열을 각각 만들에 sum이라는 값이 몇번 나올 수 있는지를 저장한다.

3. 1,2 과정은 피자 A와 B에 대해 중복되는 연산이므로 func 함수를 만들어서 중복코드를 줄인다.

4. func에서 sum을 구할 때 i를 구간의 크기로 잡는 피자 조각이 n개라면 1에서 n까지 돌아야 한다.

   j는 시작 index로 정한다. 최초 index 0부터 시작하는 i 구간만큼의 sum을 구한다.

   그 뒤의 for문은 j를 옮겨가면서 앞에는 빼주고 뒤에는 더해주는 과정이다.

   i가 최대 크기인 경우엔 이 과정은 break.

5. A,B 한개의 피자에서만 조각을 모두 가져올 수도 있으므로 func에서 sum을 구하는 도중에 답을 더해준다. 

6. Acnt,Bcnt를 모두 구했으면 곱연산으로 경우의 수를 구한다.

https://github.com/has2/Algorithm/blob/master/boj/%EC%95%84%EB%AC%B4%EA%B1%B0%EB%82%98/2632.cpp

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