알고리즘(C++) / 프로그래머스 level 2 : 짝지어 제거하기

level 2 : 짝지어 제거하기

https://programmers.co.kr/learn/courses/30/lessons/12973?language=cpp 

코딩테스트 연습 - 짝지어 제거하기

 

코드

#include <iostream>
#include <string>
#include <stack> //first in last out
using namespace std;

int solution(string s)
{
    int answer = -1;
    stack <char> st;
    for (int i = 0; i < s.size(); i++) {
        if (st.empty()) {
            st.push(s[i]);
            continue;
        }
        if (st.top() == s[i]) {
            st.pop();
        }
        else {
            st.push(s[i]);
        }
    }

    if (st.empty())
        answer = 1;
    else {
        answer = 0;
    }

    return answer;
}

int main() {
    string s = "cdcd";
    cout << solution(s) << "\n";
    return 0;
}

 

설명

first in last out

stack은 first in last out의 구조를 가지고 있다.

이런 stack을 이용하여 stack 가장 top에 저장되어 있는 알파벳과 push할 다음 자리의 알파벳을 비교하여 같을 때는 pop을 하고 같지 않을 때는 stack에 push 한다.

stack에 남아있는 알파벳이 있다면 짝지어지지 못한것이므로 0을 출력하게 된다. 

 

고찰

stack을 이용하여 구현할 수 있었다. 하지만 stack에 접근하기까지에 시간이 좀 걸렸다. 

어떤 문제에서 stack을 사용할 수 있는지 더 공부해야할 것 같다.