굳건하게

문제 : 2020 카카오 BLINE RECRUITMENT '괄호변환'

구현 문자열 스택

문제에서 정확하게 알고리즘을 명시해줘서 구현만 하면 되는 문제입니다.

1) 입력으로 들어온 문자열이 빈 문자열인지 아닌지 체크, 빈 문자열이라면 빈 문자열을 return 해줍니다.

2) 입력으로 들어온 문자열을 순회하며, '(' 와 ')' 의 개수를 count하고 빈 문자열 u에 concat을 해줍니다. 이때, '(' 와 ')' 의 개수가 같아지면 u가 균형잡힌 괄호 문자열이므로 break 해주고, 나머지 부분은 v 에 concat을 해줍니다.

3) u가 올바른 괄호 문자열인지 자료구조 stack 을 이용해 check합니다.

 3-1) u가 올바른 괄호 문자열이라면 u + solution(v) 를 return 해주면 됩니다.

 3-2) u가 올바른 괄호 문자열이 아니라면, '(' + solution(v) + ')' 와 u의 첫 번째와 마지막 문자를 제거한 나머지 부분들 뒤집어서 return 해주면 됩니다.

#include <string>
#include <vector>
#include <stack>
using namespace std;

string solution(string p) {
	string answer = "";
	string u = "", v = "";

	if (p == "")
		return answer;
	
	// u 랑 v로 나눔.
	int cnt1 = 0, cnt2 = 0;
	for (int i = 0; i < p.length(); i++) {
		if (p[i] == '(')
			cnt1++;
		else
			cnt2++;

		u += p[i];
		if (cnt1 != 0 && cnt1 == cnt2)
			break;
	}

	for (int i = u.length(); i < p.length(); i++)
		v += p[i];
	
	// u 가 올바른 괄호 문자열인지 체크하자.
	bool check = false;
	stack<char> s;
	for (int i = 0; i < u.length(); i++) {
		if (u[i] == '(')
			s.push(u[i]);
		else {
			if (s.empty()) {
				check = true;
				break;
			}
			s.pop();
		}
	}
	if (!s.empty())
		check = true;
	if (!check) { // u가 올바른 괄호 문자열
		answer = answer + u + solution(v);
	}
	else {
		string temp = "";
		for (int i = 1; i < u.length() - 1; i++)
			if (u[i] == '(')
				temp += ')';
			else
				temp += '(';
		answer = answer + '(' + solution(v) + ')' + temp;
	}
	return answer;
}

문제 : 카카오 2020 BLINE RECRUITMENT '문자열압축'

구현

 예시 5번을 잘 이해하면 쉽게 구현할 수 있는 문제입니다. 문자열의 모든 지점에서 압축크기만큼 압축을 진행할 수 있는게 아니라, 시작지점부터 압축크기만큼 잘라야 합니다.

 1 ~ (문자열의길이 / 2) 까지 각각 다 압축을 진행해보고 가장 작은 길이 값을 return 해주면 됩니다.

 p1 : 문자열의 현재 시작 지점을 가리키고 있는 포인터

 p1 에서부터 i (현재압축크기) 만큼 같은 쌍이 몇개 나오는지 count를 합니다. 이때, count 값이 1이면 자기 자신이랑만 같다는 뜻으로 압축을 할 필요가 없습니다. 따라서, p1 을 p1 + i 로 보내준 후 다시 같은 과정을 반복하면 되고, count 값이 1보다 크다면 압축을 진행할 수 있으므로 압축을 진행하고 p1 을 p1 + count * i 로 보내주면 됩니다. 

#include <string>
#include <vector>
#include<algorithm>

using namespace std;

int get_length(int n) {
	int ret = 0;
    while(n){
    	ret++;
        n /= 10;
    }
    return ret;
}

int solution(string s) {
	int answer = s.length();
	int start = 1, end = s.length() / 2;
	for (int i = start; i <= end; i++) {
		int  p1 = 0, tempAns = s.length();
		while (p1 <= s.length() - 2 * i) {
			// p1 에서부터 i개 씩 같은지 다른지 체크해보자.
			int cnt = 0, jump = 0;
			while (1) {
				bool check1 = false;
				for (int j = 0; j < i; j++) {
					if (s[p1 + j] != s[p1 + jump + j]){
						check1 = true;
						break;
					}
				}
				if (!check1) // p1에서부터 i개씩 다 같음 -> p1 + i 로 jump를 이동.
					jump += i;
				else
					break;
				cnt++;
			}
			if (cnt == 1){ // p1에서부터 i개씩 다 같은게 자기 자신 밖에 없음.
				p1 += i; // 그러면 p1 시작 위치를 그냥 이동( 압축된게없음 )
			}
			else{ // p1에서부터 i개씩 다 같은게 있음!
				p1 += cnt * i; // 일단 p1을 저 앞으로 이동
				tempAns -= i * cnt; // 답 갱신
				tempAns += get_length(cnt) + i;
			}
		}
		answer = min(answer, tempAns);
	}
	return answer;
}

 저번에 포스팅한 ERROR : ORA-12560 : TNS:protocol adapter error 와 마찬가지로 오라클 관련 프로그램들을 실행시키지 않아서 생긴 오류다.

( 해결방법 : https://travelbeeee.tistory.com/396?category=856757 )

아래의 3개 프로그램을 실행시켜야한다!

● OracleServiceXE

● OracleXEClrAgent

● OracleXETNSListener

 컴퓨터관리 -> 서비스에서 위의 3개의 프로그램을 실행시키면 다음과 같이 에러가 사라진 것을 확인할 수 있다.

문제 : https://www.acmicpc.net/problem/2458

플로이드와샬 경로탐색

 키 순서를 입력으로 받아 그래프를 그린다고 생각하자. 그러면 i번 사람에서 j번 사람으로 경로가 있다면, j번 사람이 i번 사람보다 확실히! 키가 크다는 걸 의미한다. 따라서, 우리는 K번 사람이 다른 모든 사람들과 경로가 존재한다면 키 순서를 확실히 알 수 있다. 따라서, 플로이드와샬 알고리즘으로 모든 사람에 대해서 경로를 구하고, K번 사람이 다른 모든 사람들에게 갈 수 있거나, 혹은 다른 사람들이 K번 사람으로 올 수 있는 경로가 있다면 키 순서를 확실히 알 수 있는 사람으로 간주하면 된다.

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

const int INF = 99999999;
int map[501][501];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			map[i][j] = INF;
	for (int i = 1; i <= N; i++)
		map[i][i] = 0;

	for (int i = 0, x, y; i < M; i++) {
		cin >> x >> y;
		map[x][y] = 1; // x -> y
	}

	// 플로이드와샬
	for (int k = 1; k <= N; k++)
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				map[i][j] = min(map[i][j], map[i][k] + map[k][j]);

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		bool check = true;
		for (int j = 1; j <= N; j++)
			if (map[i][j] == INF && map[j][i] == INF) {
				check = false;
				break;
			}
		if (check)
			ans++;
	}
	cout << ans;
	return 0;
}