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

짝지어 제거하기

문제 링크

짝지어 제거하기

분석

알파벳 소문자로 이루어진 문자열 s가 주어질 때, 알파벳 2개가 붙어있는 짝을 제거하는 문제입니다.

알파벳 2개가 붙어있다는 것은, 같은 문자가 연속해서 2개 등장하는 경우를 의미합니다.

붙어있는 알파벳을 제거한다면, 해당 인덱스의 값을 제거하고 공백이 없도록 앞뒤로 문자열을 이어 붙여야합니다.
이 과정을 반복해 모든 문자를 제거할 수 있다면 1을 반환하고, 제거할 수 없다면 0을 반환해야합니다.

문자열의 최대 길이는 1,000,000으로, 브루트포스 방식에서 $O(n^2)$이 되기 때문에 해결할 수 없습니다.

풀이

#include <string>
#include <stack>

using namespace std;

int solution(string s)
{
    int answer = 0;

    // 마지막에 삽입된 문자와 현재 문자를 비교하기 위한 자료구조
    stack<char> sStack;
    
    // 입력 문자열 `s`를 순회하는 반복문
    for (int i = 0; i < s.length(); ++i)
    {
        // 스택에 값이 존재하고, 값이 연속으로 존재하게 될 경우
        if (!sStack.empty() && sStack.top() == s[i])
        {
            // 기존 값을 제거 및 다음 반복 실행
            sStack.pop();
            continue;
        }
        
        sStack.push(s[i]);
    }
    
    // 스택이 비어있는 경우, 문자열의 짝이 모두 맞는 상태
    if (sStack.empty())
    {
        answer = 1;
    }

    return answer;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

• 문자열 s를 순회하는 반복문 $O(n)$

공간 복잡도는 $O(n)$입니다.

• 모든 문자가 짝이 맞지 않아 스택에 삽입되는 경우 $O(n)$

테스트 성능

정확성 테스트

테스트 1 〉 통과 (0.01ms, 4.14MB)
테스트 2 〉 통과 (0.32ms, 4.2MB)
테스트 3 〉 통과 (0.57ms, 4.16MB)
테스트 4 〉 통과 (0.44ms, 4.15MB)
테스트 5 〉 통과 (0.46ms, 4.15MB)
테스트 6 〉 통과 (0.45ms, 4.21MB)
테스트 7 〉 통과 (0.47ms, 4.2MB)
테스트 8 〉 통과 (0.46ms, 4.2MB)
테스트 9 〉 통과 (0.01ms, 4.2MB)
테스트 10 〉 통과 (0.01ms, 4.21MB)
테스트 11 〉 통과 (0.01ms, 4.16MB)
테스트 12 〉 통과 (0.01ms, 4.21MB)
테스트 13 〉 통과 (0.01ms, 4.18MB)
테스트 14 〉 통과 (0.01ms, 4.21MB)
테스트 15 〉 통과 (0.01ms, 4.2MB)
테스트 16 〉 통과 (0.01ms, 4.13MB)
테스트 17 〉 통과 (0.01ms, 4.22MB)
테스트 18 〉 통과 (0.03ms, 4.2MB)

효율성 테스트

테스트 1 〉 통과 (2.93ms, 6.66MB)
테스트 2 〉 통과 (2.93ms, 5.98MB)
테스트 3 〉 통과 (5.81ms, 6.42MB)
테스트 4 〉 통과 (5.74ms, 6.32MB)
테스트 5 〉 통과 (5.70ms, 6.32MB)
테스트 6 〉 통과 (6.27ms, 6.36MB)
테스트 7 〉 통과 (5.75ms, 6.41MB)
테스트 8 〉 통과 (4.62ms, 6.51MB)