[프로그래머스] 짝지어 제거하기

링크

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

프로그래머스

풀이

문자열을 2개씩 짝지어 제거 할수 있는데 문자열 모두를 제거 할수 있는지 없는지를 찾는 문제이다.

 

일단 일반적으로 문자열을 계속 탐색하여 2개씩 짝지어져 있다면 제거하고 또 탐색하여 제거하고

이렇게 문제를 문다면 아마도 시간초과가 날 확률이 매우매우매우 높다.

 

그러기에 문자열을 한번만 탐색하면서 풀수 있는 방법을 찾아야 하는데

이때 스택을 이용한다면 문자열을 한번 탐색하여 풀수 있게 된다.

 

1. 스택이 비어 있다면 현재 위치 문자를 push

2. 스택의 top이 현재 위치 문자와 같다면 pop

3. 스택의 top이 현재 위치 문자와 다르다면 push

문자열이 baaaab 일때

 

 

 

 문자열을 모두 탐색하였을때 스택이 비어있으면 1 스택이 비어있지 않다면 0 을 출력하면 됩니다

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 1010
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

stack<char> _stack;
int solution(string s)
{
	int s_size = s.size();

	for (int i = 0; i < s_size; i++) {
		if (_stack.empty())
			_stack.push(s.at(i));
		else if (_stack.top() == s.at(i)) {
			_stack.pop();
		}
		else {
			_stack.push(s.at(i));
		}
	}

	return (_stack.size() ? 0 : 1);
}

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

	string s; cin >> s;

	cout << solution(s);
}