작은시작

문제

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

풀이

초반부터 설계를 제대로 하고 풀지 않아서 오래 걸렸다. 

쉽게 금방 풀릴줄알아서 바로 코드에 들어간 게 문제였다. 

신경 써야 할 점은

1. 공백 또한 입력받아야 한다. (string 헤더의 getline() 사용 필요 )

2. 스택의 경우의 수를 모두 생각 ->  ')' or ']'가 등장하였을 때 스택에 문자가 있긴 한지, 있다면 그사이 문자열 또한 균형이 잡혀있는지 판단하여야 한다.

코드

#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<stack>
using namespace std;
string arr;
stack<char> st;
vector<bool> result;
int main() {


	while (1) {
		bool flag = false;
		
			//<srting> 헤더의 getline()을 활용한 공백문자 입력 포함 , 개행(enter)까지 문자를 받음 
			
			getline(cin, arr);
			
			
		if (arr.size() == 1 && arr[0]=='.') break; //종료조건

		for (int i = 0; i < arr.size(); i++) {

			if (arr[i] == '(' || arr[i] == '[') st.push(arr[i]);
			
			if (!st.empty()) { 
				if (arr[i] == ')' && st.top() == '(') {
					st.pop();
				}
				else if (arr[i] == ']' && st.top() == '[') {
					st.pop();
				}
				else if (arr[i] == ')' && st.top() != '(') {
					flag = true;
					break;
				}
				else if (arr[i] == ']' && st.top() != '[') {
					flag = true;
					break;
				}
			}
			else { //비었을때
				if (arr[i] == ')' || arr[i] == ']') {
					flag = true;
					break;
				}
			}

		
			

		}

		if (st.size() == 0 && flag == false) result.push_back(true);
		else result.push_back(false);

		//다음을 위해 스택,문자열비우기 

		while (!st.empty()) {
			st.pop();
		}
		arr.clear();

	}

	for (int j = 0; j < result.size(); j++) {
		if (result[j] == true) cout << "yes" << endl;
		else cout << "no" << endl;
	}

	return 0;
}

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

코드 풀이 

재밌는 문자열 처리 문제였습니다. 처음에는 스택을 쉽게 생각했는데 스택에서 빼고 폭발문자열(target) 과 확인하는 과정에서 어떻게 확인하고 다시 넣을지 고민했었습니다. 

그래서

1.단순히 stack 을 이용하여 하나씩 넣다가 폭발문자열의 마지막 문자를 만났을때 다시 stack에서 폭발문자열 크기만큼 빼내서 확인후 다시 넣는 풀이방법

2. vector와 idx 변수를 사용하여 stack 처럼 푸는 방법 두가지 방법으로 풀어보았습니다.

1의 방법의 경우 stack에서 다시 빼고 target문자와 확인할때 reverse함수를 사용해야합니다.

소스 코드 (stack이용)

#include<iostream>
#include<queue>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;

int main(){
	stack<char> st;
	string a, target;

	cin >> a >> target;
	string check = "";
	for (int i = 0; i < a.size(); i++) {
		st.push(a[i]);
		if (st.size() >= target.size() && st.top() == target[target.size() - 1]) { //폭탄문자열이 들어갈수 있고 마지막 문자가 폭탄문자열과 같을때
			check = "";
			for (int j = 0; j < target.size(); j++) { //꺼내서ㄱ확인
				
				check += st.top();
				st.pop();

			}
			reverse(check.begin(), check.end());
			if(check != target) {//다르면 다시 넣어야함
				for (int k = 0; k < check.size(); k++) {
					st.push(check[k]); //다시넣기
				}
			}

		}


	}
	string result;
	if (st.empty()) cout << "FRULA";
	while(!st.empty()){
		result += st.top();
		st.pop();

	}
	reverse(result.begin(), result.end());
	cout << result;


	return 0;
}

소스 코드 (vector + index 변수 사용)

#include<iostream>
#include<queue>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
char result[1000000];
int main(){
	string a, target;
	cin >> a >> target;
	int idx = 0;
	bool flag = false;
	for (int i = 0; i < a.size(); i++){
		result[idx] = a[i];
		flag = false;
		if (result[idx] == target[target.size() - 1]) {

			for (int j = 0; j < target.size(); j++) {
				if (result[idx - j] != target[target.size() - 1 - j]) {
					flag = true;
					break;
				}
			}
			if (flag == false) {
				idx -= target.size(); // 덮어쓰기위해 다시 앞으로 인덱스이동(전부사라지면 idx=-1)
			}
		}
		idx++;



	}
	if (idx == 0) cout << "FRULA";
	else {
		for (int i = 0; i < idx; i++) {
			cout << result[i];
		}
	}
	return 0;
}

www.acmicpc.net/problem/1120

코드 설명

처음에는 문제 설명대로 앞,뒤로 전부 재귀를 이용하여 넣어보고 count 하는 방법까지 풀다가 더 쉬운풀이를 생각하게되었다.

어차피 앞뒤로 넣는다고 하면 최적의 해를 넣을것이기 때문에 기존 문자열이 최대한 일치하는 개수를 찾으면된다.

따라서, 기존문자열을 한칸씩 이동시키면서 최대한 일치하는 문자개수를 찾아서 답을 구하였다.

코드

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(){
	string a = "";
	string b = "";

	cin >> a >> b;
	int n = a.size();
	int answer = 0;
	while(a.size() <= b.size()){
		int cnt = 0;
		for (int i = 0; i < a.size(); i++) {
			if (a[i] == b[i]) cnt++;
		}
		answer = max(answer, cnt);
		a.insert(0, "#");
	}

	cout << n-answer;
	return 0;
}