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

오늘은 Level-2 문제, 짝지어 제거하기 문제를 풀었습니당!

문제

설명

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

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

b aa baa → bb aa → aa →

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

제한사항

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.
  

입출력 예
s result
baabaa 1
cdcd 0

접근

처음 접근했을 때 문제 설명에 나온 방식대로 짝이 되는 것이 있으면 지우고, 처음으로 되돌아가서 짝이 되는 것을 지우는 방식을 반복했습니당

문자열이 최종적으로 비었을 때 1을 반환하고 아니면 0을 반환하는 식으로요

답안

답안 1(효율성 X)

#include <iostream>
#include <string>

using namespace std;

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

    for(size_t nIndex = 0 ; nIndex < s.size() - 1; )
    {
        if(s.size() <= 1)
            break;

        if(s[nIndex] == s[nIndex + 1])
        {
            s.erase(s.begin() + nIndex);
            s.erase(s.begin() + nIndex);
            nIndex = 0;
        }
        else
        {
            ++nIndex;
        }
    }

    if(s.empty())
        answer = 1;

    return answer;
}

으...효용성에서 탈락을 해버리네용.

아무래도 문자열의 최대 개수는 100만개인데 위의 코드는 제거하고 처음부터, 제거하고 처음부터 하는 방식이라 시간 복잡도가 대략 O(n^2) , 심할 경우 100만 * 100만회를 순회하게 되어 이런 것 같아용

그래서! 스택을 채택해봤어용!

1. 문자열 내 문자 순회
2. 스택이 비었거나 가장 위Top에 있는 문자와 현재 문자와 다르면 Push
3. 그 밖에(문자끼리 같을 경우) Pop
4. 2~3 반복
5. 최종적으로 스택이 비었다면 1을 반환, 아니면 0을 반환

이렇게 하면, 문자열 제거 후에 다시 처음으로 돌아가서 반복하지 않고, 다음 인덱스로 넘어가 수행하기 때문에 O(n) 의 시간 복잡도를 보입니당!

답안 2(진짜)

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int solution(string s)
{
    int answer = 0;
    // 홀수는 무조건 하나가 남습니다.
    if(s.empty() || s.size() % 2 != 0)
        return answer;

    stack<char> stk;
    for(size_t nIndex = 0; nIndex < s.size() ; ++nIndex)
    {
        if(stk.empty() || stk.top() != s[nIndex])
            stk.push(s[nIndex]);
        else
            stk.pop();
        
    }

    if(stk.empty())
        ++answer;

    return answer;
}

후기
실은 처음에 효율성 떨어지고 나서 투 포인터라는 기법을 활용해 풀려고 했는데 이것도 시간 초과가 떴었어용(더 틀리는건 덤!). 그때부터 점점 이 기법으로 반드시 풀어야 겠다! 라는 강박이 생겼었어용.

근데 알고보니 결국 이 기법도 O(n^2) 이였던거였습니다. 풀었다 쳐도 결국 시간 초과였던 거죠...

문득 이 문제를 풀다 평소 업무 자세에 대한 반성을 조금하게 됩니당... 반드시 내가 정한 방법으로 풀꺼야!라는 생각 때문에 속도가 더딘 적이 더러 있었으니까요

효율적인 개발 습관 그리고 시간과 노력 투자 가치가 있는 로직인지 판단하는 능력의 중요성을 새삼 깨닫게 됩니당 ㅠㅜ

https://github.com/pray92/Algorithm/blob/master/C_Plus_Plus/Programmers/RemoveWithParing.cpp