프로그래머스 - 짝지어 제거하기 (C++)

Pixabay로부터 입수된 Pexels님의 이미지 입니다.

 

---

 

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

프로그래머스

 

 이번 문제는 문자열이 주어졌을 때, 같은 알파벳이 2개씩 붙어있는 것들을 제거해나갔을 때 모든 알파벳을 제거할 수 있는지 검사하는 문제이다. 처음에는 단순무식하게 주어진 문자열 s를 구성하는 문자들을 일일이 검사하게 구현하였다. 

 

#include <iostream>
#include <string>
using namespace std;

int solution(string s)
{   
    // 만약 문자열의 길이가 홀수라면 최대한 줄여도 알파벳 하나가 남게 된다.
    if (s.length() % 2 == 1)
        return 0;
    
    bool canRemove = true;

    while(s.length() > 0 && canRemove == true)
    {
       canRemove = false;
        
        for (int i = 0; i < s.length() - 1; ++i)
        {
            if (s[i] == s[i + 1])
            {
                s = s.substr(0, i) + s.substr(i + 2);
                canRemove = true;
                break;
            }
        }
    }
        
    if (s.length() == 0)
        return 1;
    else
        return 0;
}

당연하게도 효율성 테스트에서 시간 초과가 떴다. 그렇기에 다른 방식을 생각해보았다.

 

 이번 문제는 스택을 이용할 수 있을 것이라 생각했다. 스택은 마치 프링글스 통같이 마지막에 넣은 것이 제일 위에 있는 자료구조이다. 스택을 이번 문제에서는 이렇게 이용할 수 있을 것이다.

1. 문자열 s를 구성하는 알파벳을 처음부터 끝까지 하나씩 탐색한다.
2. 현재 i번째 알파벳 s[i]의 차례이다. 만약 스택이 비어있거나, 스택의 가장 위의 알파벳이 s[i]와 다를 경우, 스택에 s[i]를 넣는다.(push)
3. 만약 그렇지 않고 스택의 가장 윗 알파벳이 s[i]와 같은 경우, 이는 문제의 "같은 알파벳이 2개 붙어 있는 짝"이므로 스택 가장 윗 알파벳을 꺼낸다.(pop) 그리고 2개의 알파벳이 같이 제거되야 하므로 s[i]는 넘긴다.

이를 구현한 코드는 아래와 같다.

 

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int solution(string s)
{
    stack<char> stk;
    
    for (int i = 0; i < s.length(); ++i)
    {
        char letter = s[i];
        
        if (stk.empty() || stk.top() != letter)
            stk.push(letter);
        else
            stk.pop();
    }
    
    if (stk.empty())
        return 1;
    else
        return 0;
}