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

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

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

 

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

int solution(string s)
{
    stack<char> st;
    int pos=0;
    while (pos<s.size()){
        if (st.empty()){
            st.push(s[pos++]);
            continue;
        }
        if (s[pos]==st.top()){
            st.pop();
        }
        else{
            st.push(s[pos]);
        }
        pos++;
    }
    if (!st.empty()){
        return 0;
    }
    else{
        return 1;
    }
}

 

처음 문제를 잘못 읽어서.. 2개 "이상" 이면 모두 제거하는 식으로 했다.. 그래서 한참 헤매고.. 반례를 보다가.. 문제 조건이 "2개 붙어 있는 짝" 임을 캐치했다.. 문제좀 잘읽자....

 

처음에는 stack사용 안하고 배열을 순회하면서 문자열을 떼고, 붙이고.. 등을 반복했는데 시간초과. 

stack을 사용하면 O(N) 만에 해결 가능하다.

 

스택이 비면->문자를 넣어주고

스택의 탑과 지금 넣으려는 애가 같으면->스택의 탑을 pop 해준다(짝지어 제거하는 방식)

서로 다르면=>그 문자를 push 해준다

다음 문자로 이동해서 다음 과정을 반복..

 

스택이 비면 모두 제거할 수 있다는 뜻이므로 1을 리턴.

 

stack을 사용해서 한 번의 스캔 만에 되도록 하는 것이 중요하다.