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

• 짝지어 제거하기

• darklight

  sublimevimemacs

  C++ 

문제 설명

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

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

b aa baa → bb aa → aa →

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

제한사항

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

---

입출력 예

sresult

baabaa	1
cdcd	0

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.
입출력 예 #2
문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.

 

 

 

풀이및 생각)

맨처음에는 정렬후 중복된건 삭제해줄려고햇는데 2번쨰 예시가 cdcd엿고 정렬시에는 제거할수있는 문자열이 되므로 안되고 

다음으로 생각한것은 string s에 erase를 사용하면 되지않나 싶었는데 

효율성에서 막히게 되었다.

그래서 어떤 컨테이너를 써야할거같은데 어떤것을 사용할까 싶었는데

vector 도 생각해보다 보니 또 삭제가 오래걸렷다는것을생각해보니 안되고

또다른 string에 해주는것도 효율성에서 통과하지않았고

list의 유니크 함수를 써볼려고햇는데

aa 라면 a가 남는데 a가 남는게 유니크를 써준 문자인지 확인하는것도 아니라는생각이들어서 

그다음으로 스택을 써보게 되었다.  

b    top b

b a     top a

b a  << a. push 전 체크를 할때 top 값이 a 이므로 중복체크가 되고 넘어가기에 빠른거같다. 

 

 

 

스택으로 사용

string s = { "baabaa" };
int answer = 0;
 
stack<char> ss;
for (int i = 0; i < s.length(); i++)
{
    if (ss.empty() || ss.top() !=s[i])
    {
        ss.push(s.at(i));
    }
    else
    {
        cout << endl;
        cout << ss.top()<<" ";
        cout << s[i];
        ss.pop();
    }
}
 
if (ss.empty())
{
    answer = 0;
}
else
{
    answer = 1;
}
 
cout << answer;