Programmers - 괄호 변환

---

title: Programmers - 괄호 변환
date: 2022-06-26
tags:

• Algorithm

---

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

문제 요약

'(' 와 ')'로만 이루어진 문자열이 들어온다. '('와 ')'의 개수는 같으며 ')'가 맞는 쌍 없이 먼저 나오면 이는 올바른 문자열이 아니다. 문제에서 주어진 조건에 맞게 문자열을 변환하여 return한다.

문제 풀이

조건이 길게 서술되어 있으나, 천천히 읽어보면 별로 어렵지 않다.

1. empty string은 그대로 empty string으로 return
2. 앞에서부터 '('와 ')'의 개수가 같은 문자열 u, 나머지 문자열 v로 분리한다. u가 올바른 문자열(쌍이 순서대로 나왔을 때)이라면 v에 대해서만 재귀적으로 처리한다.
3. u가 올바른 문자열이 아니라면, '(' + v에 대한 재귀적 처리 + ')' + u의 '('과 ')'를 서로 바꾼 후 첫 문자와 마지막 문자를 제외한 문자열 을 반환한다.
   조건을 확실하게 이해하고, 이를 그대로 프로그램으로 작성하면 된다.
   문자열의 길이가 1k 이하이므로 O(n^3)까지 가능하다. 이는 일반적인 재귀 알고리즘을 사용해도 문제가 해결 가능함을 의미하며, 또한 매우 효율적인 알고리즘을 사용하면 성능 부분에서 좋은 점수를 얻을 수 있다는 의미이다.

처음에는 post의 가장 하단에 존재하는 나쁜 프로그램을 작성하였다. 재귀를 위한 함수를 선언하였으며, 기존 문자열과 분리될 위치를 넘겨준다.
재귀를 위한 함수에서는 u에 해당하는 문자열이 올바른 문자열인지에 따라 케이스를 나누어 처리하지만, 매우 비슷한 처리이기에 좋은 프로그램이 아니다.
문자열의 길이가 1k 이하이므로 성능 자체는 괜찮았으나, 읽기 싫은 프로그램을 작성하였다. AC 이후 발견한 프로그램에서 놀라운 경험을 하였다.
solution 함수 자체를 재귀 함수로 이용하여 문제를 해결한 것이다. solution 함수는 시스템에서 호출하는 것으로 단정짓고 이를 사용하지 않았는데, 이러한 편견을 아예 깨버린 것이다.
해당 프로그램의 아이디어를 이용하여 solution 함수 그 자체를 재귀로 사용하는 프로그램을 작성하였다. 훨씬 간결하여 가독성이 좋은 프로그램으로 바뀌었다.
나쁜 프로그램은 bool 변수를 이용하면 조금 더 좋은 프로그램으로 바꿀 수 있으나, solution을 재귀로 사용하지 않는 한 여전히 좋은 프로그램으로 보이지 않는다.
성능 자체는 거의 차이가 없지만 좋은 프로그램이 무엇인지 다시 한 번 느낄 수 있었다.

solution을 재귀로 사용하는 수정한 프로그램

#include <string>

using std :: string ;

bool bIsRightString ( string str )
{
    int iCnt = 0 ;
    int iLen = str.size () ;
    const char * cpTemp = str.data () ;

    for ( int i = 0 ; i < iLen ; ++i )
    {
        if ( '(' == cpTemp [ i ] )
            ++ iCnt ;
        else
            -- iCnt ;

        if ( iCnt < 0 )        // ) come first, it's not right string
        {
            return false ;
        }
    }

    return true ;
}

string solution ( string p )
{
    string answer = "" ;
    int iLen = p.size () ;
    const char * cpTemp = p.data () ;
    int iCnt = 0 ;
    int iIndex = 0 ;
    string u ;
    string v ;



    if ( ( 0 == iLen ) || ( bIsRightString ( p ) ) )
        return p ;

    for ( int i = 0 ; i < iLen ; ++i )
    {
        if ( '(' == cpTemp [ i ] )
            ++ iCnt ;
        else
            -- iCnt ;

        if ( 0 == iCnt )
        {
            u = p.substr ( 0 , i + 1 ) ;        // Divide
            v = p.substr ( i + 1 , iLen ) ;

            break ;
        }
    }

    if ( bIsRightString ( u ) )                    // If u is right string, then transform v and return
    {
        return u + solution ( v ) ;
    }

    cpTemp = u.data () ;
    iLen = u.size () ;
    for ( int i = 1 ; i < iLen - 1 ; ++i )
    {
        if ( '(' == cpTemp [ i ] )
            u [ i ] = ')' ;
        else
            u [ i ] = '(' ;
    }

    return "(" + solution ( v ) + ")" + u.substr ( 1 , iLen - 2 ) ;        // u is not right string, so transform all
}

나쁜 프로그램

#include <string>

using std :: string ;

bool bIsRightString ( string str )
{
    int iCnt = 0 ;
    int iLen = str.size () ;
    const char * cpTemp = str.data () ;

    for ( int i = 0 ; i < iLen ; ++i )
    {
        if ( '(' == cpTemp [ i ] )
            ++ iCnt ;
        else
            -- iCnt ;

        if ( iCnt < 0 )        // ) come first, it's not right string
        {
            return false ;
        }
    }

    return true ;
}

string getRightString ( string strInput , int iDivideIndex )        // 0 to iDivideIndex = u // v = iDivideIndex + 1 ~
{
    string strReturn = "" ;
    int iLen = strInput.size () ;
    int iCnt = 0 ;
    const char * cpTemp = strInput.data () ;

    if ( 0 == iLen )
        return strInput ;

    if ( bIsRightString ( strInput.substr ( 0 , iDivideIndex + 1 ) ) )
    {
        strReturn = strInput.substr ( 0 , iDivideIndex + 1 ) ;

        for ( int i = iDivideIndex + 1 ; i < iLen ; ++i )
        {
            if ( '(' == cpTemp [ i ] )
                ++ iCnt ;
            else
                -- iCnt ;

            if ( 0 == iCnt )
            {
                strReturn += getRightString ( strInput.substr ( iDivideIndex + 1 , strInput.size () ) , i - iDivideIndex - 1 ) ;

                break ;
            }
        }
    }
    else
    {
        strReturn.push_back ( '(' ) ;

        for ( int i = iDivideIndex + 1 ; i < iLen ; ++i )
        {
            if ( '(' == cpTemp [ i ] )
                ++ iCnt ;
            else
                -- iCnt ;

            if ( 0 == iCnt )
            {
                strReturn += getRightString ( strInput.substr ( iDivideIndex + 1 , strInput.size () ) , i - iDivideIndex - 1 ) ;

                break ;
            }
        }

        strReturn += ')' ;

        for ( int i = 1 ; i < iDivideIndex ; ++i )
        {
            if ( '(' == cpTemp [ i ] )
                strReturn += ')' ;
            else
                strReturn += '(' ;
        }
    }


    return strReturn ;
}

string solution ( string p )
{
    string answer = "" ;
    int iLen = p.size () ;
    const char * cpTemp = p.data () ;
    int iCnt = 0 ;
    int iIndex = 0 ;



    for ( int i = 0 ; i < iLen ; ++i )
    {
        if ( '(' == cpTemp [ i ] )
            ++ iCnt ;
        else
            -- iCnt ;

        if ( 0 == iCnt )
        {
            answer = getRightString ( p , i ) ;

            return answer ;
        }
    }


    answer = getRightString ( p , iLen - 1 ) ;    // Divide into p , empty string

    return answer ;
}