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

프로그래머스 2017 팁스타운 : 짝지어 제거하기

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12973

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

---

문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

---

풀이 1

#include <string>
#include <iostream>

using namespace std;

int solution(string s)
{   
    while(s!=""){
        string newStr = "";
        bool isDel = false;
        
        for(int i=1; i<s.size(); i++){
            if(s[i-1]==s[i]){
                isDel = true;
                s[i-1] = ' ';
                s[i] = ' ';
                break;
            }
        }
        
        if(isDel){
            for(int i=0; i<s.size(); i++){
                if(s[i] != ' ')
                    newStr += s[i];
            }
            s = newStr;

        } else {
            break;
        }
        
    }
    
    if(s=="") return 1;
    else return 0;
    
}

효율성 에러가 와장창..^^

시간 초과 에러..!! 이런 경우는 처음부터 다시 풀어야 하기에 당황했다,,

문자열 중복을 체크해가며 하나하나 제거해 newStr에 다시 저장하는 무한 루프를 도는 것이 문제이다 ㅠㅠ
너무 깊게 생각한 것 같다. 하지만 난 이런 생각밖에 안 나는걸,,

 

 

풀이 2

#include <string>
#include <stack>

using namespace std;

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

문자열 제거를 사용하기 보다는 stack 을 사용해 for문을 한 번만 돌도록 구현했다.
아까 코드보다 훨씬 간결해 짐을 확인할 수 있다.

 

드디어 성공~!