검지offer-3-면접12:1부터 최대 n자리까지 인쇄

제목

분석

면접관의 함정에 뛰어들어 대수를 고려하지 않았다

문자열에 디지털 덧셈을 시뮬레이션하는 해법

문제를 디지털 배열로 바꾸는 해법 귀속 코드를 더욱 간결하게

테스트 용례 코드

본제 시험점

확장

관련 제목

제목.

숫자 n을 입력하여 1에서 최대 n까지의 십진수를 순서대로 인쇄합니다.예를 들어 3을 입력하면 1, 2, 3이 가장 큰 세 자리, 즉 999까지 출력된다.

분석하다.

면접관의 함정에 빠져 대수 문제를 고려하지 않았다

제목은 보기에 매우 간단하다.이 문제를 본 후 가장 생각하기 쉬운 방법은 먼저 가장 큰 n자리를 구한 다음에 하나의 순환으로 1부터 하나씩 인쇄하는 것이다.따라서 다음과 같은 코드를 쉽게 쓸 수 있다.

void print1ToMaxOfNDigits_1( int n )
{
    int number = 1;
    int i = 0;
    while( i++ < n )
        number *= 10;
    for( i=1;i<number; ++i )
        cout << i << "\t";
}

처음 보면 문제가 없는 것 같지만 이 문제를 자세히 분석하면 면접관이 n의 범위를 정하지 않은 것을 발견할 수 있다.n을 크게 입력했을 때 가장 큰 n자리를 구하려면 정형(int)이나 장정형(long long)이 넘칠까요?대수 문제를 고려해야 한다는 얘기다.

문자열에 디지털 덧셈을 시뮬레이션하는 해법

분석을 통해 이 문제를 해결하려면 큰 수를 표현해야 한다고 생각할 수 있다.가장 자주 사용하고 가장 쉬운 방법은 문자열이나 수조로 큰 수를 표현하는 것이다.다음은 문자열로 대수 고문단을 해결한다.
문자열로 숫자를 표시할 때 가장 직관적인 방법은 문자열 안의 모든 문자가'0'에서'9'사이의 어떤 문자로 숫자 중의 한 사람을 나타내는 것이다.숫자가 가장 큰 것은 n자리이기 때문에 길이 n+1의 문자열이 필요합니다. (문자열 중 마지막은 끝 기호 '\0' 입니다.)실제 숫자가 n자리가 되지 않을 때 문자열의 앞부분에서 0을 보충합니다.
우선 우리는 문자열의 모든 숫자를 '0' 으로 초기화한 다음에 매번 문자열에 표시된 숫자에 1을 더해서 인쇄한다.따라서 우리는 두 가지 일을 할 수 있다. 하나는 문자열이 표현한 숫자에 아날로그 덧셈을 하는 것이고, 다른 하나는 문자열이 표현한 숫자를 출력하는 것이다.위의 분석을 바탕으로 다음과 같은 코드를 작성할 수 있습니다.

void print1ToMaxOfNDigits( int n )
{
    if( n <= 0 )
        return;
    char *number = new char[ n+1 ];
    memset( number, '0', n );
    number[ n ] = '\0';

    //Increment            number   1
    while( !Increment( number ) )
    {
        PrintNumber( number ); //   number
    }
    delete []number;
}

인크리에이션과 관련해서는 number에서 1을 늘리는 것을 언제 멈추는지, 즉 최대 n자리인'999...99'(n개 9)에 도달했는지 알아야 한다.가장 간단한 방법은 매번 증가할 때마다 라이브러리 함수strcmp를 호출하여 수치를 나타내는 문자열인number와 가장 큰 n자리 '999... 99' 를 비교하는 것이다. 만약 같으면 이미 가장 큰 n자리 수에 이르렀고 증가를 중지하는 것이다.strcmp를 호출하는 것은 간단하지만, 길이가 n인 문자열의 시간 복잡도는 O (n) 이다.
"999...99"에 1을 더할 때만 첫 번째 문자(아래 0 표시)에 진위가 생기고, 다른 모든 경우 첫 번째 문자에 진위가 생기지 않는다.따라서 1을 추가할 때 첫 번째 문자에 진위가 생겼다는 것을 발견하면 가장 큰 n자리수입니다. 이 때 Increment는true를 되돌려줍니다. 따라서 함수Print1ToMax OfNdigits의while 순환이 종료됩니다.매번 1씩 증가한 후에 가장 큰 n자리까지 왔는지 아닌지를 신속하게 판단하는 것은 본 문제의 작은 함정이다.다음은 Increment 함수의 참조 코드로, 최대 n 자릿수에 도달했는지 O(1) 시간으로 판단할 수 있습니다.

bool Increment( char * number )
{
    bool isOverflow = false;
    int nTakeOver = 0;
    int nLength = strlen( number );
    for( int i=nLength -1; i>=0; i-- )
    {
        int nSum = number[i] - '0' + nTakeOver ;
        if( i==nLength - 1 )
            nSum++;
        if( nSum >= 10 )
        {
            if( i==0 ) isOverflow = true;
            else
            {
                nSum -= 10;
                nTakeOver = 1;
                number[i] = '0' + nSum;
            }
        }
        else
        {
            number[i] = '0' + nSum;
            break;
        }
    }
    return isOverflow;
}

다음은 문자열로 표시된 숫자를 어떻게 인쇄하는지 고려합니다.라이브러리 함수 printf는 문자열을 쉽게 출력할 수 있지만, 이 문제에서 printf를 호출하는 것은 가장 적합한 해결 방안이 아닙니다.앞에서 언급한 바와 같이 숫자가 n자리가 부족할 때 우리는 숫자의 앞에서 0을 보충하고 인쇄할 때 이 보충된 0은 인쇄해서는 안 된다.예를 들어 3을 입력할 때 숫자 98은 문자열로 098을 표시하는데 098을 직접 출력하면 우리의 습관에 맞지 않는다.이를 위해 함수PrintNumber를 정의했습니다. 이 함수에서 문자열의 끝까지 첫 번째 0이 아닌 문자를 만났을 때만 인쇄를 시작합니다.

void PrintNumber( char * number )
{
    bool isBeginning0 = true;
    int nLength = strlen( number );
    for( int i=0; i<nLength; ++i）
    {
        if(isBeginning0 && number[i] !='0' )
            isBeginning0 = false;
        if( !isBeginning0 )
            cout << number[i] ;
    }
    cout << "\t" ;
}

문제를 디지털 배열의 해법으로 바꾸어 코드를 더욱 간결하게 하다

상술한 사고방식은 비교적 직관적이지만 정수의 덧셈을 모의했기 때문에 코드가 좀 길다.면접 몇 십 분 만에 이렇게 긴 코드를 완전하고 정확하게 쓰는 것은 많은 지원자들에게 쉬운 일이 아니다.다음에 우리는 사고방식을 바꾸어 이 문제를 고려한다.만약 우리가 숫자 앞에서 0을 보충한다면 n위의 모든 십진수는 사실 n개가 0에서 9까지의 전체 배열이라는 것을 발견할 수 있을 것이다.즉, 우리는 숫자의 한 사람 한 사람을 0-9에서 한 번 배열하면 모든 십진수를 얻을 수 있다.다만 우리가 인쇄할 때, 숫자가 앞에 배열되어 있는 0은 인쇄하지 않는다
전체 배열은 귀환으로 쉽게 표현할 수 있으며 숫자의 한 자리 한 자리가 0-9의 한 수일 수도 있고 다음 자리를 설정할 수도 있다.귀환이 끝나는 조건은 우리가 이미 숫자의 마지막 자리를 설정한 것이다.

void Print1ToMaxOfNDigits( int n )
{
    if( n<= 0 )
        return;
    char *number = new char[ n+1 ];
    number[ n ] = '\0';

    for( int i=0; i<10; ++i )
    {
        number[0] = i + '0';
        Print1ToMaxOfDigitsRecursively( number, n, 0 );
    }
    delete []number;
}

void Print1ToMaxOfNDigitsRecursively( char* number, int length, int index )
{
    if( index==length-1 )
    {
        PrintNumber( number );
        return;
    }
    for( int i=0; i<10; ++i )
    {
        number[index+1] = i+'0';
        Print1ToMaxOfNDigitsRecursively( number, length, index+1 );
    }
}

테스트 용례 & 코드

(1) 기능 테스트(1, 2, 3 입력...)
(2) 특수 입력 테스트(입력-1,0)

본제 시험장

(1) 대수 문제를 해결하는 능력.면접관이 이 문제를 낼 때 지원자가 큰 문제라는 것을 깨닫고 적당한 데이터 표시 방식을 정의하여 큰 문제를 해결할 수 있기를 기대한다.
(2) 만약에 지원자가 첫 번째 사고방식, 즉 숫자에 1씩 인쇄하는 사고방식을 채택한다면 면접관은 그가 가장 큰 n자리에 도달했는지 판단할 때 사용하는 방법을 주목할 것이다.지원자는 서로 다른 방법의 시간 효율 차이가 매우 크다는 것을 주의해야 한다
(3) 지원자가 두 번째 사고방식을 채택하면 면접관은 그가 귀속 방법으로 문제를 해결하는 능력을 고찰한다.
(4) 지원자가 숫자를 출력할 때 숫자 맨 앞에 있는 0이 출력되는지도 주목한다.지원자들이 소프트웨어를 디자인하고 개발할 때 사용자의 사용 습관을 고려하는지 알 수 있다.일반적으로 우리의 소프트웨어 디자인과 개발은 대부분의 사용자의 인간관계 습관에 부합해야 한다.

본제 확장

앞의 코드에서, 우리는 모두char형 문자로 십진수 숫자의 한 자리를 표시한다.8개bit의char형 문자는 최대 256개의 문자를 나타낼 수 있지만, 10진수 숫자는 0-9의 10개의 숫자에 불과하다.따라서char형 문자열로 십진수를 표시하는 숫자는 메모리를 충분히 이용하지 못해 낭비가 있었다.더 효율적인 방식으로 대수를 나타낼 수 있습니까

관련 문제

이 함수에서 임의의 두 정수의 덧셈을 실현할 수 있는 함수를 정의합니다.두 개의 수를 입력하는 크기 범위를 한정하지 않았기 때문에, 우리도 그것을 대수 문제로 처리해야 한다.앞의 코드의 첫 번째 사고방식에서 문자열이 표시하는 숫자에 1을 더하는 기능을 실현했다. 우리는 이 사고방식을 참고하여 두 숫자의 더하기 기능을 실현할 수 있다.또 주의해야 할 문제가 하나 더 있다. 만약 입력한 숫자에 마이너스가 있다면 우리는 어떻게 처리해야 합니까?