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

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

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

---

 

-풀이-

문자열의 길이가 최대 1000000이므로, O(N²)으로는 풀면 무조건 떨어질것이다.

그래서 생각해본 방법은 1번 인덱스부터 시작해서, 자신의 뒤의 알파벳과 같으면 str.substr을 이용하여 자르고 붙인뒤, 인덱스를 다시 설정하여 O(N)으로 짜보려 했지만, substr의 시간복잡도가 O(N)이여서 총 O(N2)이 되므로 효율성에서 불통이 된다.

 

그래서 생각을 해본것이, 어차피 자신의 바로 뒷쪽과 비교를 하면되므로, stack을 이용해보았다.

1. stack이 비어있거나, stack의 top(현재 글자의 뒷글자) 와 같지 않다면 push를 해준다.

2. stack의 top(현재 글자의 뒷글자) 와 같다면 pop을 해서 짝지어 제거를 해준다.

3. 마지막까지 탐색 후 , stack이 비어있다면, 모두 제거할 수 있으므로 1을, 비어있지 않다면 0을 return 해준다.

 

예시로 "baabaa"를 시뮬레이션 해보자면,

오른쪽으로 쌓여나가는 stack이 있다 해보자.

 

0번째 인덱스)

스택이 비어있으므로, push를 해준다.

현재 스택: "b"

 

1번째 인덱스)

스택의 top 인 "b"와 현재 인덱스의 글자인 "a"가 같지 않으므로 , push 해준다.

현재 스택: "ba"

 

2번째 인덱스)

스택의 top인 "a"와 현재 인덱스의 글자인 "a"가 같으므로, pop해준다.

현재 스택: "b"

 

3번째 인덱스)

스택의 top인 "b"와 현재 인덱스의 글자인 "b"가 같으므로, pop해준다.

현재 스택 :" " 

 

4번째 인덱스)

스택이 비어있으므로, push해준다.

현재 스택 : "a"

 

5번째 인덱스)

스택의 top인 "a"와 현재 인덱스의 글자인 "a"가 같으므로, pop해준다.

현재 스택: " "

 

마지막까지 검사 후, 스택이 비어있으므로, 짝지어 모두 제거할 수 있는 문자열이므로 result=1이 된다.

 

-코드-

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

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