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

klean·2021년 5월 1일
0

문제요약

  • 문자열에서 같은 문자가 2개씩 나오는 것을 발견하면 짝지어 제거합니다.
  • 제거된 빈 공간을 없는 걸로 치고 또 짝지어 제거할 수 있으면 제거합니다.
  • 짝지어 제거해서 이 문자열을 없앨 수 있는지 여부를 구하세요.

아이디어

stack을 활용한 제거 시뮬레이션.
stack을 2개 사용하여 뚜껑과 밑통으로 활용하고
각 stack의 top을 비교대상으로 삼았다.

일치하면 각 stack을 pop하여 새로운 top들이 탄생하고
일치하지 않으면 바닥 stack top이 뚜껑 stack으로 이동한다.

마지막에 전부 없앨 수 있는지의 여부는 뚜껑 stack이 비어있는가를 사용했다.
왜냐면 뚜껑 stack의 경우 붙어있는 원소들끼리 일치하는 경우는 없기 때문이다.

테케

삽질

굳이 길이 가변 vector(python list)를 활용하여 시뮬레이션

pop 연산을 해가며 제거된 문자열을 압축하는 방법.

장점

편하다. 빈공간이 생기는 것에 대한 걱정이 없음

치명적 단점

pop 연산에 O(N)이 발생한다. => O(N^2)

길이 고정 vector를 활용하여 시뮬레이션

pop 연산을 하며 문자열을 압축하는 것 대신 ' '문자로 채움으로써 사라진 문자임을 표시.

장점

같은지 비교하는 위치 i(앞에거) j(뒤에거) 가 총 길이가 변하지 않으니가 움직이는 걸 좀 더 안정적으로 구현할 수 있다.

치명적 단점

이미 지워진 자리 ' '를 만났을 때...
b__a__ab 에서 a들끼리 지워진 후 b______b 가되어 b들끼리 지워져야한다.
j의 경우 내가 지우지 못한 방향으로 가니까 그냥 산술적으로 커지면 되지만
i의 경우 내가 지웠던 부분들을 건너 뛰어야 하기(나는 while문을 사용했다.) 때문에 O(N)이 발생한다.

소스코드

정답을 받기까지 2시간 정도 소요됐다.

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

string stack_to_str(stack<char> s){
    string ret = "";
    while(!s.empty()){
        ret+=s.top();
        s.pop();
    }
    return ret;
}

int solution(string str)
{
    int answer = 0;
    //문제와의 지우는 순서 일치를 위해 거꾸로 넣기
    stack<char> q;
    for(int i = str.size()-1;i>=0;i--){
        q.push(str[i]);
    }
    stack<char> sq;//subq
    while(!q.empty()){
        if(!sq.empty()){
            char a = sq.top();
            char b = q.top();
            //cout<<"검사중! "<<a<<" , "<<b<<endl;
            if(a == b){
                sq.pop();
                q.pop();
            }
            else{
                q.pop();
                sq.push(b);
            }
        }
        else{
            int o = q.top();
            q.pop();
            sq.push(o);
        }
        /*
        cout<<stack_to_str(q)<<endl;
        cout<<stack_to_str(sq)<<endl;
        cout<<"=================="<<endl;
        */
    }
    
    if(sq.empty()){
        answer = 1;
    }
    return answer;
}

0개의 댓글