Level 2. 짝지어 제거하기

Level 2. 짝지어 제거하기

 

 

첫 번째 문제는 정답을 맞으나 효율성 테스트에서 실패했다.

 

앞에서부터 같은 두 개의 문자를 찾아 제거하며 반복하는 방식이다.

 

최악의 경우 O(n²)이 소요되기 때문인 것 같다.

 

#include <iostream>

using namespace std;

int solution(string s)
{
    auto find_pair = [](string& s) -> size_t
    {
        size_t len = s.length() - 1;

        for (int i = 0; i < len; ++i)
            if (s[i] == s[i + 1])
                return i;

        return string::npos;
    };

    s += '0';

    for (size_t pos = find_pair(s); pos != string::npos; pos = find_pair(s))
        s.erase(pos, 2);

    return (s == "0");
}

 

생각해보니 괄호 짝 맞추기처럼 스택을 활용하면 효율적으로 간단하게 풀 수 있는 문제였다.

 

#include <iostream>
#include <stack>

using namespace std;

int solution(string s)
{
    stack<char> stck;

    for (char c : s)
        if (!stck.empty() && stck.top() == c)
            stck.pop();
        else
            stck.emplace(c);

    return stck.empty();
}