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

문제 : 짝지어 제거하기

문제 설명

 

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

 

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

 

제한사항

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

 

 분석

 처음엔 그냥 무턱대고 무식하게 풀어봤다. 

int solution(string s)
{
	int cnt = s.size();
	while (cnt--)
	{
		for (size_t i = 0; i < s.size() - 1; i++)
		{
			if (s[i] == s[i + 1])
			{
				if (i > 0)
				{
					string tmp_1 = s.substr(0, i);
					string tmp_2 = s.substr(i + 2);
					s = tmp_1 + tmp_2;
					break;
				}
				else
				{
					s = s.substr(i + 2);
					break;
				}
			}
		}
		if (s.size() == 0) break;
	}

	if (s.size() == 0) return 1;
	else return 0;
}

하지만 효율성에서 통과하지 못했다. ( O(n^2) )

 

그래서 stack을 이용해 단일 for문으로 문제를 해결했다.

 

 구현

int solution(string s)
{
	stack<char> c;
	for (size_t i = 0; i < s.size(); i++)
	{
		if (c.empty() || c.top() != s[i]) c.push(s[i]);
		else if (c.top() == s[i]) c.pop();
	}

	if (c.empty()) return 1;
	else return 0;
}

int main()
{
	cout << solution("cdcd"); // 0
	return 0;
}