[프로그래머스/C++ 문제 풀이] Lv. 2 - 짝지어 제거하기

문제 설명

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

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

b aa baa → bb aa → aa →

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

제한 사항

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

입출력 예

 

입출력 예 #1
위의 예시와 같습니다.

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

---

문제 풀이

이번 문제는 알파벳을 짝지어 같은 알파벳이 연속으로 나오는 경우 제거해야하는 문제입니다.

 

이번 문제와 같이 [짝짓기] 문제가 나온다면 우선적으로 Stack 자료구조를 생각해볼 필요가 있습니다.

 

Stack은 FILO(First In Last Out) 구조로, 알맞는 짝을 지어 제거하는 문제에서 마지막 들어온 요소와 다음 요소를 비교하기 매우 편한 자료구조이기에 저의 경우 스택을 사용해 문제를 바로 해결하게 되었습니다.

 

간단히 풀이 방법에 대해 설명하자면 다음과 같습니다.

1. 스택이 비어있지 않고, 스택의 최상단(마지막)요소가 들어올 문자열과 같은지 체크하기

2. 체크한 결과가 참이라면 스택의 최상단 요소를 제거하기

3. 체크한 결과가 거짓이라면 짝짓기에 실패한 것으로 생각하여 스택에 문자 추가하기

4. 모든 문자 순회 후 스택이 비어있다면 모두 제거에 성공한 것으로 생각하기

정답 코드

풀이 시간 : 3m 10s

#include <string>
#include <stack>

using namespace std;

int solution(string s)
{
    int answer = -1;

    stack<char> stk;
    
    for (int i = 0; i < s.length(); i++)
    {
        // 스택의 크기 체크 및 스택의 최상단 요소가 s[i]와 동일하다면?
        if (!stk.empty() && stk.top() == s[i])
        {
            // 같은 알파벳이 연속으로 들어온 것으로 생각하고 스택의 최상단 요소를 제거합니다.
            stk.pop();
        }
        // 스택의 최상단 요소와 같지 않거나 스택의 크기가 0인 경우
        else
        {
            // 스택에 s[i]번째 알파벳을 추가합니다.
            stk.push(s[i]);
        }
    }
    
    // 위 반복문을 통해 모든 문자열을 순회한다면 폭파가 되는 문자는 제거될 것입니다.
    // * 즉, 스택이 비어있으면 모든 문자가 제거된 것으로 생각할 수 있습니다.
    answer = stk.empty() ? 1 : 0;

    return answer;
}