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

문제

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

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

 

문제 내용

문자열에서 같은 글자 2개가 붙어있으면 제거해 주면 된다. (계속해서 지워나가야 함)

b aa baa -> bb aa -> aa -> 

위와 같이 연달아 같은 문자가 있으면 제거해주면 된다.

끝까지 제거했을 때, 문자열을 모두 제거할 수 있으면 1을, 문자열이 남게 되면 0을 return 한다.

 

문제 풀이

맨처음에는 문자열에서 붙어있는 곳을 찾아서 그 부분만 빼고 삭제하는 방법으로 구현을 했다.

이 풀이는 반복문을 여러 번 돌아야 하기 때문에 효율성 체크에서 실패가 떴다. (해당 코드가 궁금하면 더보기 클릭)

정확성 체크는 통과, 효율성 체크는 실패하는 코드

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

string removeDuplicateChar(string s) {
    string newStr = "";
    for (int i = 0; i < s.size() - 1; i++) {
        if (s[i] == s[i + 1]) {
            i++;
            continue;
        }
        newStr += s[i];
    }

    if (s[s.size() - 2] != s[s.size() - 1]) { // 마지막 글자 처리
        newStr += s[s.size() - 1];
    }

    if (s.size() == newStr.size()) { // 길이가 같으면 중복 제거가 안 됐다는 뜻
        return "-1";
    } else
        return newStr;
}

int solution(string s) {
    if (s.size() % 2 == 1) // 길이가 홀수이면 바로 0 리턴
        return 0;

    while (true) {
        if (s.size() == 0)
            return 1; // 모두 제거

        string newStr = removeDuplicateChar(s);
        if (newStr == "-1") {
            return 0;
        } else {
            s = newStr;
        }
    }
}

 

그래서 방법을 찾아보니 stack을 사용하면 되었다.

stack에 집어넣을 때마다, 가장 위의 글자와 일치하는지를 비교하면 된다.

이 방법은 반복문을 여러번 돌지 않으니, 시간초과가 발생할 일도 없었다.

 

코드

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

int solution(string s) {
    if (s.size() % 2 == 1) // 길이가 홀수이면 바로 0 리턴
        return 0;

    stack<char> st;
    int idx = 0;

    while (idx != s.size()) {
        if (!st.empty() && st.top() == s[idx]) {
            st.pop();
        } else {
            st.push(s[idx]);
        }
        idx++;
    }

    if (st.empty())
        return 1;
    else
        return 0;
}