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

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

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

 

풀이

 

처음엔 그냥 while문안에서 for문으로 쌍을 찾는 방식으로 코드를 작성하였더니 효율성이 하나도 통과하지 못하는 처참한 상황이 생겼습니다.

 

그래서 스택을 사용해서 O(n)으로 해결될 수 있도록 코드를 새로 작성하였습니다.

 

우선 문자열 s를 for문을 이용해 처음부터 차례로 탐색합니다.

1. stack이 비어있는 경우, 현재 문자를 stack에 푸시합니다.
2. 비어있지 않은 경우 stack의 top값과 현재 문자를 비교합니다.
3. 둘이 동일한 경우 stack에서 top값을 pop합니다.
4. 동일하지 않은 경우 stack에 현재 문자를 push합니다.

for문을 완료한 후 stack이 비어있는지 확인하고 비어있는 경우엔 모두 삭제한 것이므로 answer = 1이 됩니다.

 

#include <iostream>
#include <string>
#include <algorithm>
#include <stack>

using namespace std;

int solution(string s)
{
    int answer = 0;
    stack<char> del;
    int s_len = s.length();
        
    for(int i=0; i<s_len; i++){
        if(del.empty())
            del.push(s[i]);
        
        else{
            char check = del.top();
            if(check == s[i])
                del.pop();
            else
                del.push(s[i]);
        }
    }

    if(del.empty())
        answer = 1;
    
    return answer;
}