문제 설명
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.
예를 들어, 문자열 S = baabaa 라면
b aa baa → bb aa → aa →
의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.
제한 사항
- 문자열의 길이 : 1,000,000이하의 자연수
- 문자열은 모두 소문자로 이루어져 있습니다.
풀이
vector를 이용하면 간단하게 풀 수 있는 문제이다.
주어진 문자열 중 동일한 문자 2개가 붙어있는 경우 제거할 수 있기 때문에 모든 문자열에 대해 검사해야 한다.
또한, 문자를 제거한 경우 문자열이 달라지기 때문에 다시 검사해야 된다.
하지만, 이렇게 모두 검사하게되면 시간 초과가 발생한다.
시간 초과를 해결하기 위해서는 vector를 사용하면 된다.
문자열에서 짝을 지어 문자가 제거될 때, 제거된 문자 다음에 오는 문자와 제거된 문자 이전 문자가 짝을 지을 수 있는지 판단하면 문제를 풀 수 있다.
예를 들어, b aa baa 에서 'aa'가 제거되면 b baa가 된다.
제거된 'aa'이전의 문자인 b와 이후의 문자 b가 짝이 된다면 동일한 방법으로 제거하고, 그렇지 않다면 vector에 저장하여 다음 문자를 검사하면 된다.
그리고 효율을 올리기 위해 하나의 트릭을 사용할 수 있다.
문자열의 길이가 홀수라면 절대로 모두 제거될 수 없다.
전체 코드
#include <iostream>
#include<string>
#include<vector>
using namespace std;
int solution(string s)
{
if(s.size() % 2 == 1) return 0;
vector<char> unremoved;
unremoved.push_back(s[0]);
for(int i = 1; i < s.size(); i++)
{
if(unremoved.empty())
{
unremoved.push_back(s[i]);
continue;
}
if(s[i] == unremoved.back()) unremoved.pop_back();
else unremoved.push_back(s[i]);
}
return unremoved.size() == 0;
}