Programmers - 큰 수 만들기

---

title: Programmers - 큰 수 만들기
date: 2022-06-23
tags:

• Algorithm

---

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

문제 요약

주어진 문자열 형식의 숫자에서 k개의 문자를 제거하여 만들 수 있는 가장 큰 숫자를 문자열로 return한다.

문제 풀이

문자열의 길이는 1M까지 되므로 1s 기준에서는 O(nlogn)을 넘으면 안 된다.
하지만 문자열을 두 번 확인할 필요 없이 앞에서부터 확인하면 되는 문제이다.
지운 문자의 개수를 카운트하며 앞의 문자를 지웠을 때 훨씬 좋은 수가 되는지 확인한다.
9가 나올 경우 확인을 멈춰야 쓸모없이 탐색하는 시간이 매우 줄어든다.
문자를 다 지우지 않았는데 loop가 끝나면 일정 위치부터는 내림차순으로 되어있으므로 뒤에서부터 지운다.
문자를 다 지우고 loop가 끝나면 확인하지 않은 남은 문자들을 문자열에 추가하면 된다.

프로그램

#include <string>

using std :: string ;

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



    while ( ( iCnt < k ) && ( iIndex < iLen ) )
    {
        if ( '9' == cpTemp [ iIndex ] )                    // Biggest, don't check
        {
            answer += cpTemp [ iIndex ++ ] ;
            continue ;
        }

        iTargetIndex = iIndex ;
        for ( int i = iIndex + 1 ; ( i <= iIndex + k - iCnt ) && ( i < iLen ) ; ++i )
        {
            if ( cpTemp [ iTargetIndex ] < cpTemp [ i ] )
            {
                iTargetIndex = i ;

                if ( '9' == cpTemp [ iTargetIndex ] )    // If find 9, then don't need to check other numbers
                    break ;
            }
        }

        if ( iIndex != iTargetIndex )                    // erase iIndex to iTargetIndex - 1
        {
            iCnt += iTargetIndex - iIndex ;
            iIndex = iTargetIndex ;

            answer += cpTemp [ iIndex ++ ] ;

            continue ;
        }

        // iIndex == iTargetIndex
        answer += cpTemp [ iIndex ++ ] ;
    }

    if ( iCnt < k )                                        // If append too many number, then erase the rest
        answer = answer.substr ( 0 , iLen - k ) ;
    else                                                // Erased, so append the rest
    {
        for ( int i = iIndex ; i < iLen ; ++i )
        {
            answer += cpTemp [ i ] ;
        }
    }

    return answer ;
}