[Programmers] 짝지어 제거하기

https://school.programmers.co.kr/learn/courses/30/lessons/12973

프로그래머스

 

---

 

문제 해결 과정

착안

문자를 짝끼리 비교하여 같은 문자면 지우는 과정을 반복하면, 지워지는 문자가 있을 때 처음부터 다시 과정을 반복해야하므로 시간 복잡도 측면에서 매우 비효율적이다. 따라서, 스택(stack) 자료 구조의 후입선출(LIFO) 원리를 활용해 문제를 해결한다.

 

구현

주어진 문자열에 대해 앞에서부터 문자 하나씩 잘라서, 현재 스택의 top과 비교해 두 문자가 같으면 문자 하나를 스택에서 꺼내고 그렇지 않다면 스택에 자른 문자를 넣는 과정을 반복한다.

 

문자열의 끝까지 위 과정을 반복했을 때, 스택이 비어있다면 짝지어 제거 가능한 문자열이고 그렇지 않다면 남는 문자열이 있는 경우이다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <string>
#include <stack>

using namespace std;

int solution(string s)
{
    if (s.size() % 2)
        return 0;
    
    stack<char> words;
    for (char c : s)
    {
        if (!words.empty() && words.top() == c)
            words.pop();
        else
            words.push(c);
    }
    
    return words.empty();
}

 

실행 결과