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

냥

정답률 높은순으로 푸는중인데

이제 점점 정답률 50%대에 가까워지는중 .. 안돼 ~ ..

 

무튼

풀이 과정

시행착오?

첨엔 생각하기 귀찮아서 투 포인터로 풀려고했당..

포인터 두개 써서 둘이 일치하면 해당 자리의 char을 뭐 0으로 바꾸거나 해서 하는식으로..

근데 그러면 좀 복잡해지더군 ㅋㅎ

 

가령,,

a 0 0 b b a ~~ ..

위와 같은 상황이랄까 할때

뒤에서 따라오는 역할의 포인터가, 만약 0을 가리킬때? 이런 조건을 다 분기처리해야해서

 

쏘 귀찮 ㅋ 오히려 배로 귀찮아지길래

아 레벨투인데 절대이럴리 없다 걍 스택 써야겠다 ㅋ 했음

 

결론

스택으로 구현해서 풀었다

흔히 계산기? 전위표기 후위표기 (prefix postfix) 같은거 하듯이~~

 

반복문 내에서 i 증가시키면서, 가리키는 곳과 스택의 back의 값이 불일치 할때마다 그 값들을 스택에 넣어서

마지막에 스택이 empty가 아니면 0을 리턴하는 방식!

 

정답 코드

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

int solution(string s)
{
    int answer = 1;
    vector<char> stack;
    char before=s[0];
    stack.push_back(before);
    
    for(int i=1;i<s.length();i++){
    	// 문자열 끝 안났는데 stack 비어있을 경우
        if(stack.empty()){
            stack.push_back(s[i]);
            continue;
        }
        before=stack.back();
        if(before==s[i]){ // 일치
            stack.pop_back();
        }else{ //불일치
            stack.push_back(s[i]);
        }
    }
    
    if(!stack.empty())
        answer=0;
    return answer;
}