[프로그래머스] Level.2 2017 팁스다운- 짝지어 제거하기

코딩테스트 연습 - 짝지어 제거하기

 

문제설명

입출력예

 

첫번쨰 풀이- 정확성 통과, 효율성 실패

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


int solution(string s)
{
	int answer = 0, i = 0;
	string a = ""; string b = "";

	while (1) {
		
		if (s.size() == 0) answer = 1;

		if (s.size() == 0 || s.size() <= i)
			break;

		if (s[i] == s[i + 1]) {
			a = s.substr(0, i);
			b = s.substr(i + 2, s.size() - 1);
			s = a + b;
			i = 0;
		}	
		else i++;
			
	}
	return answer;
}

 

 

두번째풀이- 통과

스택을 이용해서 풀었다. 같은 알파벳이 들어오면  스택에 있는 알파벳을 pop해준다.

주어진 문자열의 길이 만큼 다 수행해서 스택에 들어있는 알파벳이 존재하지 않으면 답은 1 아니면 0이다.

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

int solution(string s)
{
	int answer = 0;
	stack<char>st;
	for (int i = 0;i < s.length();i++) {
		if (st.size()!=0 && st.top() == s[i]) st.pop();
		else st.push(s[i]);
	}
	if (st.size() == 0) answer = 1;
	return answer;
}