Programmers - 110 옮기기

---

title: Programmers - 110 옮기기
date: 2022-08-14
tags:

• Algorithm

---

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

문제 요약

0과 1로만 구성된 문자열이 존재한다.
문자열 중 일부가 110일 경우, 이를 통째로 옮겨 원하는 위치에 넣을 수 있다. 이로 인해 새로운 110이 생성되면 동일한 작업을 반복할 수 있다.
이러한 작업을 통해 만들 수 있는 문자열 중 사전에서 가장 앞에 나오는 (수로 변환시 가장 작은) 문자열을 return한다.

문제 풀이

string의 overhead를 간과하였다가 삽질을 한 문제이다.
처음에는 110을 앞에서부터 탐색하다가 발견할 경우 이를 제외한 남은 문자열 중 삽입할 장소를 찾았다.
삽입할 위치를 기준으로 substr을 이용하여 앞은 이미 검사가 끝났기에 놔두고, 검사를 해야하는 뒤 문자열을 다시 재귀 호출을 이용하여 문자열을 구했다.
이 결과 110 처리 1회 (함수 실행 1회)에 O(n^2)의 시간 복잡도를 보였으며, 아슬아슬하게 통과하거나 TLE가 발생하였다.


O(n)의 알고리즘은 결국 한 번의 순회를 통해 110 검출 및 삽입이 필요하다.
이전의 삽입 알고리즘은 앞에서부터 여러 조건이 존재하였으나, 오히려 뒤에서 보면 0이 처음 발견될 때 해당 0 바로 뒤, 0이 없다면 맨 앞에 삽입하여야 한다.
이렇게 할 경우 110 처리가 한 번 이루어지면 이후에 삽입할 위치는 계속 맨 뒤에 존재하는 110으로 인하여 해당 위치 뒤에 삽입이 된다는 것이다.
결국 110이 몇 개가 되었든 삽입 처리는 한 번에 가능하다는 뜻이다.
새로 삽입한 110은 다시 쓰이려면 해당 110을 그대로 사용하여야 하며, 이는 불필요한 작업이므로 검사할 필요가 없다는 뜻이다.
그렇기에 O(n)의 순회시 110을 모두 찾아낸다면 재귀 호출 없이 문자열을 구성할 수 있다.
이를 위하여 stack을 사용하였다.


문자열의 앞에서부터 한 개씩 stack에 넣은 후, 상태를 갱신한다.
기본 상태는 0으로, 1이 발견될 때마다 1씩 상태가 더해지며 최대 2까지만 갱신된다.
상태가 2일 때 발견되는 1은 아무런 영향을 주지 않는다.
상태가 2일 때 0이 발견되면 110을 발견한 것이며, 이외의 경우에 0이 발견되면 상태를 0으로 바꾼다.
110을 발견하면 stack에서 110을 pop한 후, 새로 stack의 top이 되는 수를 확인하여 상태를 갱신해준다.
이를 통해 110을 발견 - 제거 의 routine으로 110을 전부 찾아낼 수 있었다.
stack에 남아있는 문자들은 110이 제거된 문자열이며, LIFO이므로 꺼내는 순서는 문자열의 역순이다.
고로 처음에 0이 발견이 되면 바로 110의 역순인 011을 count한 개수만큼 return할 문자열에 추가해준다.
전부 1이라면 stack의 모든 문자를 return할 문자열에 추가한 후 011을 추가해준다.
이제 문자열이 역순으로 구성되었으므로, 다시 이를 std :: reverse 함수를 이용하여 뒤집어준다.

프로그램

#include <string>
#include <vector>
#include <stack>
#include <algorithm>

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

string strGetMinimumString ( string strTarget )
{
    int iStringSize = strTarget.size () ;
    int iCount = 0 ;
    int iConditionCount = 0 ;
    stack < int > stackCheck ;
    string strReturn ;



    for ( int i = 0 ; i < iStringSize ; ++i )
    {
        stackCheck.emplace ( strTarget [ i ] ) ;

        if ( ( iConditionCount <= 1 ) && ( '1' == stackCheck.top () ) )
            ++ iConditionCount ;
        else if ( ( 2 == iConditionCount ) && ( '0' == stackCheck.top () ) )
        {
            stackCheck.pop () ;
            stackCheck.pop () ;
            stackCheck.pop () ;

            char cTemp = '\0' ;
            iConditionCount = 0 ;
            ++ iCount ;

            if ( ! stackCheck.empty () )
                cTemp = stackCheck.top () ;

            if ( '1' == cTemp )
            {
                stackCheck.pop () ;
                iConditionCount = 1 ;


                if ( ( ! stackCheck.empty () ) && ( '1' == stackCheck.top () ) )
                {
                    iConditionCount = 2 ;
                }

                stackCheck.emplace ( cTemp ) ;

                continue ;
            }
        }
        else if ( '0' == stackCheck.top () )
        {
            iConditionCount = 0 ;
        }
    }

    while ( ! stackCheck.empty () )
    {
        if ( ( 0 != iCount ) && ( '0' == stackCheck.top () ) )
        {
            for ( int i = 0 ; i < iCount ; ++i )
            {
                strReturn += "011" ;
            }

            iCount = 0 ;
        }

        strReturn += stackCheck.top () ;
        stackCheck.pop () ;
    }
    if ( 0 != iCount )
    {
        for ( int i = 0 ; i < iCount ; ++i )
        {
            strReturn += "011" ;
        }
    }

    std :: reverse ( strReturn.begin () , strReturn.end () ) ;


    return strReturn ;
}

vector < string > solution ( vector < string > s )
{
    vector < string > answer ;
    int iStringSize = s.size () ;



    for ( int i = 0 ; i < iStringSize ; ++i )
    {
        answer.emplace_back ( strGetMinimumString ( s [ i ] ) ) ;
    }

    return answer ;
}

int main ()
{
    vector < string > s = solution ( { "1100111011101001" }) ;
}