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

문제는 다음과 같습니다.

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

프로그래머스

 

풀이 코드는 다음과 같습니다.

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

문제 자체가 쉬워서 처음에는 단순 반복문만으로 해결하려고 했습니다만 조건에서 문자열의 길이가 1,000,000 만큼 될 정도로 굉장히 길어 단순 반복문만 사용하면 효율성에서 광탈할 수 있습니다.

단순 반복문으로 한 건 다음과 같습니다.

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

int solution(string s)
{
    int answer = -1;
    while(true)
    {
        bool check(true);
        if(s.size()==0)
        {
            answer=1;
            break;
        }
        for(int i{1};i<s.size();i++)
        {
            char c1=s[i-1];
            char c2=s[i];
            if(c1==c2)
            {
                check=false;
                s.erase(s.begin()+i-1);
                s.erase(s.begin()+i-1);
            }
            
        }
        if(check)
        {
            answer=0;
            break;
        }
    }

    return answer;
}

이 방법은 for문을 끝날 때까지 계속해서 돌아야 하기 때문에 문자열이 길어질수록 시간 복잡도가 기하급수적으로 늘어난다는 단점이 있습니다.

위의 방법인 자료구조 (stack)을 사용하면 귀찮은 작업 없이 for문을 한 번만 돌아서 확인할 수 있으므로 시간 복잡도를 줄일 수 있습니다.

백준과 달리 프로그래머스는 시간제한을 알려주지 않기 때문에 제한사항을 잘 읽어서 어떤 방식으로 풀 지 정해야 함을 알게 되었고 문제를 대충 보지 않고 조금 더 꼼꼼히 봐야겠다고 느끼게 된 문제인 것 같습니다.