Programmers - 브라이언의 고민

---

title: Programmers - 브라이언의 고민
date: 2022-08-31
tags:

• Algorithm

---

https://school.programmers.co.kr/learn/courses/30/lessons/1830

문제 요약

기존의 단어에 여러 규칙을 적용하여 새로운 문자열을 만들어 광고를 하는 것을 발견하였다.
각 문자열의 기존 문자열을 찾아낼 수 있다면 해당 문자열을, 규칙에 부합하면 "invalid"를 return한다.

문제 풀이

약 한달 전에 시도하였다가 실패한 문제이다.
조금 더 general하게 함수를 선언한 후, 함수를 적극적으로 이용하여 문제를 풀어 예외 처리가 되는 케이스를 최대한 줄이고자 하였다.


소문자의 개수를 전부 센다. 2개일 경우 두 규칙 모두 적용이 가능할 수 있으며, 이외의 경우에는 1번 규칙만 적용할 수 있다.
우선 소문자의 개수가 2개가 아닌 소문자에 대하여 1번 규칙을 적용한다.
2개씩의 동일한 간격이어야 하며, 이 때는 오로지 단어를 구성하는 대문자만 존재하여야 한다.
1번 규칙을 적용가능할 때 이를 적용하고, 적용한 단어의 양끝에 .을 붙인다.
공백으로 붙여도 되나, 이 문제에서 공백은 일반적으로 서로 다른 단어임을 나타낼 때 사용하였다.
1번 규칙을 적용한 단어에 2번 규칙을 적용할 수 있기에, 이를 구분하기 위하여 다른 문자를 사용하였다.
이후 남은 소문자에 대하여 2번 규칙을 적용한다.
AqSwDwFqG와 같은 경우 w에 대해서 1번 규칙, q에 대해서 2번 규칙을 적용하면 올바른 문자열을 만들어낼 수 있다.
아마 과거에는 이러한 경우를 생각하지 않고 전부 2번 규칙을 적용하여 틀린 것으로 추측이 된다.
.의 개수와 위치 또한 중요하기에 이를 따로 count하며, 소문자가 발견되면 우선 1번 규칙을 적용한다.
1번 규칙을 적용하여 남은 소문자가 없고, .의 처리 또한 정상적으로 이루어지면 이 단어에 2번 규칙을 적용한다.
모든 규칙을 적용한다면 공백이 매우 많은 문자열이 생긴다. 불필요한 공백을 없애준 후, 만들어진 광고 문구를 return한다.


이 문제를 풀었던 것이 큰 도움이 되었다.
함수를 미리 잘 구성하였다면 어디서든 이 함수를 사용할 수 있어야 한다.
이 덕분에 2번 규칙을 적용하던 중 1번 규칙을 적용할 수 있었다.

프로그램

#include <string>
#include <vector>

using std :: string ;
using std :: vector ;

string strGetRule1 ( string & strAnswer , int iStartIndex , int iCount )
{
    string strReturn = "" ;

    for ( int i = 0 ; i < iCount + 1 ; ++i )
    {
        strReturn += strAnswer [ iStartIndex + ( i << 1 ) - 1 ] ;

        if ( ' ' == strReturn [ i ] )                                            // Empty space must not be here
            return "invalid" ;
        if ( ( 'a' <= strReturn [ i ] ) && ( strReturn [ i ] <= 'z' ) )            // Small letter must not be here
            return "invalid" ;
    }

    return strReturn ;
}

bool bAdoptRule1 ( string & strAnswer , char cTarget , int iCount )
{
    int iStringSize = strAnswer.size () ;
    int iStartIndex = -1 ;
    int iFormerIndex ;
    int iCheckCount = 0 ;



    for ( int i = 0 ; ( i < iStringSize ) && ( iCheckCount < iCount ); ++i )
    {
        if ( cTarget == strAnswer [ i ] )
        {
            if ( -1 == iStartIndex )
            {
                iStartIndex = i ;
                iFormerIndex = i ;
            }
            else
            {
                if ( 2 != i - iFormerIndex )        // Gap must be 2
                    return false ;
                else
                    iFormerIndex = i ;
            }

            ++ iCheckCount ;
        }
        else if ( ( -1 != iStartIndex ) && ( ( 'A' > strAnswer [ i ] ) || ( strAnswer [ i ] > 'Z' ) ) )
            return false ;
    }

    if ( ( 0 == iStartIndex ) || ( iFormerIndex + 1 == iStringSize ) )        // Must letter at front and back
        return false ;
    if ( ( ( 'A' > strAnswer [ iStartIndex - 1 ] ) || ( strAnswer [ iStartIndex - 1 ] > 'Z' ) )
      || ( ( 'A' > strAnswer [ iFormerIndex + 1 ] ) || ( strAnswer [ iFormerIndex + 1 ] > 'Z' ) ) )
          return false ;

    string strRule1 = strGetRule1 ( strAnswer , iStartIndex , iCount ) ;

    if ( 0 == strRule1.compare ( "invalid" ) )        // Found empty space or small letter, can't adopt rule1
        return false ;


    strAnswer = strAnswer.substr ( 0 , iStartIndex - 1 ) + "." + strGetRule1 ( strAnswer , iStartIndex , iCount ) + "." + strAnswer.substr ( iFormerIndex + 2 , iStringSize - iFormerIndex - 2 ) ;

    return true ;
}

bool bAdoptRule2 ( string & strAnswer , char cTarget , vector < int > & vAlphabetCount )
{
    vAlphabetCount [ cTarget - 'a' ] = 0 ;
    int iStartIndex = -1 ;
    int iEndIndex = -1 ;
    int iLeftDotIndex = -1 ;
    int iRightDotIndex = -1 ;
    int iStringSize = strAnswer.size () ;



    for ( int i = 0 ; i < iStringSize ; ++i )
    {
        if ( cTarget == strAnswer [ i ] )
        {
            if ( -1 == iStartIndex )
                iStartIndex = i ;
            else
            {
                iEndIndex = i ;

                break ;
            }
        }
        else if ( ( -1 != iStartIndex ) && ( '.' == strAnswer [ i ] ) )
        {
            if ( ( -1 == iLeftDotIndex ) && ( iStartIndex + 1 == i ) )
                iLeftDotIndex = i ;
            else if ( ( -1 != iLeftDotIndex ) && ( -1 == iRightDotIndex ) )
                iRightDotIndex = i ;
            else                                                                // Other condition not exist
                return false ;
        }
        else if ( ( -1 != iStartIndex ) && ( ' ' == strAnswer [ i ] ) )                                            // Empty space must not be here
            return false ;
        else if ( ( -1 != iStartIndex ) && ( 'a' <= strAnswer [ i ] ) && ( strAnswer [ i ] <= 'z' ) )            // This must be rule1, or wrong string
        {
            vAlphabetCount [ strAnswer [ i ] - 'a' ] = 0 ;

            if ( ! bAdoptRule1 ( strAnswer , strAnswer [ i ] , 2 ) )            // If false, can't adopt rule1
                return false ;

            i -= 2 ;
        }
    }

    if ( iStartIndex + 1 == iEndIndex )
        return false ;
    if ( ( -1 != iLeftDotIndex ) && ( ( -1 == iRightDotIndex )
                                    || ( iRightDotIndex + 1 != iEndIndex ) ) )
        return false ;

    strAnswer = strAnswer.substr ( 0 , iStartIndex ) + " " + strAnswer.substr ( iStartIndex + 1 , iEndIndex - iStartIndex - 1 ) + " " + strAnswer.substr ( iEndIndex + 1 , iStringSize - iEndIndex - 1 ) ;

    return true ;
}

string strRemoveSpace ( string strAnswer )
{
    string strReturn = "" ;
    int iEmptySpaceIndex = -1 ;
    int iStringSize = strAnswer.size () ;



    for ( int i = 0 ; i < iStringSize ; ++i )
    {
        if ( ( 'a' <= strAnswer [ i ] ) && ( strAnswer [ i ] <= 'z' ) )
            return "invalid" ;
        else if ( ( -1 == iEmptySpaceIndex ) && ( ( ' ' == strAnswer [ i ] ) || ( '.' == strAnswer [ i ] ) ) )
        {
            iEmptySpaceIndex = i ;
        }
        else if ( ( 'A' <= strAnswer [ i ] ) && ( strAnswer [ i ] <= 'Z' ) )
        {
            if ( 0 < iEmptySpaceIndex )
            {
                strReturn += ' ' ;
            }

            iEmptySpaceIndex = -1 ;
            strReturn += strAnswer [ i ] ;
        }
    }

    return strReturn ;
}

string solution ( string sentence )
{
    string answer = sentence ;
    vector < int > vAlphabetCount ( 26 , 0 ) ;
    int iSentenceSize = sentence.size () ;
    const char * cpSentence = sentence.data () ;



    for ( int i = 0 ; i < iSentenceSize ; ++i )
    {
        if ( ( 'a' <= cpSentence [ i ] ) && ( cpSentence [ i ] <= 'z' ) )            // Small letter
        {
            ++ vAlphabetCount [ cpSentence [ i ] - 'a' ] ;
        }
        else if ( ' ' == cpSentence [ i ] )        // Empty space must be deleted
            return "invalid" ;
    }

    for ( int i = 0 ; i < 26 ; ++i )
    {
        if ( ( 0 != vAlphabetCount [ i ] ) && ( 2 != vAlphabetCount [ i ] ) )        // Only rule 1
        {
            if ( ! bAdoptRule1 ( answer , 'a' + i , vAlphabetCount [ i ] ) )        // If false, can't adopt rule1
                return "invalid" ;
        }
    }
    for ( int i = 0 ; i < 26 ; ++i )
    {
        if ( 2 == vAlphabetCount [ i ] )
        {
            if ( ! bAdoptRule2 ( answer , 'a' + i , vAlphabetCount ) )                // If false, can't adopt rule2
                return "invalid" ;
        }
    }

    return strRemoveSpace ( answer ) ;
}