백준 Q1748 수 이어 쓰기

in Algorithm on baekjoon


문제

https://www.acmicpc.net/problem/1748
1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.
1234567891011121314151617181920212223…
이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다.

출력

첫째 줄에 새로운 수의 자릿수를 출력한다.

풀이

문제는 간단했다. 다만, 이를 어떻게 생각할 것인가가 진정한 문제이다.

문제 그대로 어떤 숫자 N을 입력하면 N번에 거쳐서 나온 숫자들을 이어 붙인다 생각하신다면… 되기는 할 것이지만, 문제에서 시간 제한은 0.15초이다. N 최대 1억번이라 할 때 이 시간 제한은 혹독한 편이다.

그렇다면 수학적인 규칙을 찾아 구현하여 시간을 줄이는 게 최종 목표가 될 것이다.

1부터 N까지 자리수를 붙이는 원리를 생각하자면…

  • 1 ~ 9는 한자리 (9-1+1) * 1 = 9
  • 10 ~ 99는 두자리 (99 - 10 + 1) * 2 = 180
  • 100 ~ 999는 세자리 (999 - 100 + 1) * 3 = 2700
    …
  • 10,000,000 ~ 99,999,999는 여덟자리 (99,999,999 - 10,000,000 + 1) * 8 = 720,000,000

이런 순으로 자리수가 더해질 것이다.

이 중 N은 몇 자리(n)인지 확인하고 1자리 부터 ~ n-1자리 까지의 자리 수 합을 구한 다음, n자리에서 n자리의 시작지점(10 ^ (n-1))부터 N까지의 숫자 개수 * n자리 수를 더해 주면 될 것이다. 예외는 마지막 1억이 되시겠다. 이 경우 1억 이전에 모든 자리의 수 다 더한 다음 1억의 자리수 9만 더하면 될 것이다.

이를 요약하자면 다음과 같다.

  • N의 자리 수를 확인한다.
  • 1부터 (N의 자리 수 - 1) 까지 자리 수를 먼저 계산하여 합한다.
    [(각각 자리수의 최대값 - 최소값 + 1) * 자리 수]
  • N의 자리 수는 N 까지의 자리 수 계산하여 합한다.
    [(N - N 자리 수 최소값 + 1) * N 자리 수]
  • 최대값 1억은 9만 더해준다.

이를 구현하자면 다음과 같다.

private static int getTotalLength(int n){
    int totalLength = 0;
    // N의 자리수 계산 = nLength
    int nLength = Integer.toString(n).length();

    for(int numberLength = 1; numberLength <= nLength; numberLength++){
        // numberLength 자리 수 중 최소값 최대값
        int nthNumStart = (int) Math.pow(10, numberLength - 1);
        int nthNumEnd = (int) Math.pow(10, numberLength) - 1;

        // 1 ~ nLength - 1 까지의 자리 수 계산 = (최대 - 최소 + 1) * 자리 수
        if(numberLength != nLength){
            totalLength += (nthNumEnd  - nthNumStart + 1) * numberLength;
        }
        // 1억이 되는 경우에 대해서만 +9
        else if(numberLength == 9){
            totalLength += Integer.toString(n).length();
            break;
        }
        // nLength 자리 수 에서 N 까지의 자리 수 계산 = (N - 최소 + 1) * 자리 수
        else {
            totalLength += (n  - nthNumStart + 1) * numberLength;
        }
    }

    return totalLength;
}

만약 자리 수에 집중하여 수의 규칙이 잘 생각이 안난다면, 이 문제를 쪼개서 생각해보는 것도 나쁘진 않다. 자리 수 문제를 달리 생각하자면 각 자리의 범위를 세워서 구하는 문제로 관점을 다르게 생각할 수 있다.
위의 내용과 비슷해 보이지만, 1억의 경우 따로 범위를 다르게 지정해 주면서 해결한 케이스 이다.

private static int getTotalLength(int n){
    int[] startArray = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
    int[] endArray = {9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 100000000};

    int totalLength = 0;
    for(int i = 0; i < 9; i++){
        // 자리수 범위
        int start = startArray[i];
        int end = endArray[i];

        // n의 범위를 계산하여 자리수 계산
        if(n >= start && n <= end){
            // 해당 범위 내에 있는 경우: (n - n의 자리 시작점 + 1) * n의 자리수 (현재 자리 수 계산)
            totalLength += (n  - start + 1) * Integer.toString(start).length();
        }
        else if(n > end){
            // 해당 범위보다 큰 경우: 해당 범위내 숫자 개수 * 해당 범위의 자리수 (이전 자리 수 계산)
            totalLength += (end  - start + 1) * Integer.toString(start).length();
        }
        else{
            // 해당 범위보다 작은 경우: 해당 안 됨.
            break;
        }
    }

    return totalLength;
}

결론

알고리즘에 필요한 기법들 이나 규칙 없이도 문제를 해결할 수 있다. 초중고때 배운 수학적인 생각을 응용한다면 이런 문제도 풀 수 있다.
사실 알고리즘이란 게, 문제 해결 방식으로 넓게 생각하면 우리는 알고리즘이라는 것을 어렸을 적 기초 학습을 통해 접해온 것이라 개인적으로 생각한다. ‘수학 배워다 어디다 쓰냐?’란 질문에 우리는 문제 해결을 통해 실제로도 많이들 사용하고 있다.
그리고 이러한 해결 방법을 생각해내는 것이야 말로 개발자가 하던 일이자, 해야만 하는 일이다.