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

짝지어 제거하기

 

문제 설명

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

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

b aa baa → bb aa → aa →

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

 

제한사항

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

 

입출력 예

s	result
baabaa	1
cdcd	0

 

시작 코드

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

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

    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    cout << "Hello Cpp" << endl;

    return answer;
}

 

나의 풀이

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

int solution(string s)
{
    stack<char> st;

    for (int i = 0; i < s.size(); ++i)
    {
        if (st.empty())
        {
            st.push(s[i]);
        }
        else if (st.top() == s[i])
        {
            st.pop();
        }
        else
        {
            st.push(s[i]);
        }
    }

    return st.empty();
}

 

코드 분석

char형으로 stack을 만들고 for문을 돌립니다. 안에서는 if elseif문이 있고 if문부터 보면 스택이 비어있다면 스택에 해당 요소를 추가하고, 스택의 맨 윗 요소를 가리키는 top의 요소가 현재 요소와 같다면, 스택의 요소를 pop합니다. 두 조건에 만족하지 않는다면 스택에 현재 요소를 추가합니다. if문을 빠져나가면서 반복문을 계속 돌고 반복문을 빠져나오면 스택이 비어있는지 판단하는 empty를 통해 bool값을 리턴합니다.

 

풀이 설명

문제가 원하는 것은 짝지어 제거하기, 그에 대한 설명은 문제에 나와있듯 문자열에서 같은 문자열이 붙어있는 것을 찾아 제거하는 방식입니다. 기본적으로 주어진 문자열을 순회하면서 앞뒤 문자열을 비교하여 같으면 묶어서 제거하는 방식입니다. baabaa로 실행해보면, for문으로 돌면서 처음 b를 만나면 스택이 비어있기 때문에 스택에 추가되고, 다음 a를 만나면 else를 통해 다시 스택에 추가됩니다. 다음 a를 만나면 else if문에 의해서 스택에 있는 a와 같기 때문에 스택을 pop하여 스택에는 b만 남습니다. 이후 뒤에는 같은 구성이므로 똑같이 진행됩니다. 그러면 aa가 계속 지워져 bb가 남고 이어서 bb도 짝이 지어졌기 때문에 스택은 비게 됩니다. 스택이 비었으므로, st.empty()는 true로 1을 반환합니다.

 

<NEXT>

오늘은 정답률 74%의 2017 팁스타운 문제인 "짝지어 제거하기"를 다뤄보았습니다. 다음에는 완전탐색 문제 "카펫"을 다뤄보겠습니다. 감사합니다.