Programmers - 짝지어 제거하기

---

title: Programmers - 짝지어 제거하기
date: 2022-06-20
tags:

• Algorithm

---

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

문제 요약

데이터로 들어온 문자열에서 같은 문자가 서로 붙어있다면 붙어있는 2개의 문자를 제거한다. 모든 문자가 제거가 되면 1을, 안 되면 0을 return한다.

문제 풀이

문자열의 길이는 최대 1M이므로 1s라 가정하면 O(nlogn)이 한계이다. 앞에서부터 탐색하며 제거가 되면 바로 앞의 문자부터 체크를 시작하여야 불필요한 탐색을 하지 않는다.
처음에는 string.erase 함수를 이용하였으나, 시간이 너무 오래 걸려 효율성 테스트를 하나도 통과하지 못하였다. 스택 방식으로 수정하였다.
순서대로 스택에 집어 넣으며, 체크해야할 문자와 stack.top 이 같다면 pop을 하고 다음 문자를 처리한다.

프로그램

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

using std :: string ;
using std :: stack ;

int solution ( string s )
{
    int i = 0 ;
    const char * cpTemp = s.data () ;
    int iLen = s.size () ;
    stack < int > sPile ;
    bool bEmplace = true ;



    if ( 1 == iLen % 2 )                            // Odd number, can't remove all
        return 0 ;


    while ( i != iLen )
    {
        if ( sPile.empty () || bEmplace )
            sPile.emplace ( cpTemp [ i ++ ] ) ;

        if ( i == iLen )
            return 0 ;

        if ( sPile.top () == cpTemp [ i ] )            // Same, pop
        {
            sPile.pop () ;

            ++i ;
            bEmplace = false ;

            continue ;
        }

        bEmplace = true ;
    }

    if ( ( i == iLen ) && ( sPile.empty () ) )
        return 1 ;


    return 0 ;
}