백준 수 이어쓰기1 1748

2020-10-20

백준, 알고리즘, 연산

1. 문제 링크

1.1. 백준 수 이어쓰기1 1748 문제

1.1.1. 문제

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223…

이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

1.1.2. 입력

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

1.1.3. 출력

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

1.1.4. 예제 입력 1

120

1.1.5. 예제 출력 1

252

1.2. 컴퓨팅적 사고

1~N까지의 값을 수를 이어서 쓰면 하나의 수를 얻을때 몇자리수인지를 구하는문제입니다.
알고리즘 사고를 말하기 앞서, String VS StringBuilder, StringBuffer의 차이를 확인하고 지나가겠습니다.

String VS StringBuilder, StringBuffer
String 클래스 불변 객체이기 때문에 문자열 연산에서 객체를 계속 생성하므로 성능이 떨어지지만 조회와 멀티스레드 환경에서 큰 이점을 가지고 있습니다.

이에 반해,StringBuffer 클래스와 StringBuilder 클래스는 문자열 연산이 자주 발생할 때 문자열이 변경가능한 객체이므로 이점을 가지고 있습니다.

즉, StringBuffer와 StringBuilder 차이점은 동기화 지원 유무이고 동기화를 고려하지 않는 환경에서 StringBuilder가 성능이 더 좋고, 동기화 멀티스레드 환경에서는 StringBuffer을 사용하는것이 좋습니다.

모든 경우로 가능할까? 브루트 포스?
N의 범위를 살펴보면 N(1≤N≤100,000,000) 의 조건을 가지고 있습니다. 1초에 1억까지 연산이 가능하므로 1초안에 처리 될 수 있어야합니다.

즉, 모든 경우의 수를 O(N)만큼 진행하면 브루트포스로 진행이 가능하지만, 문자열 연산에서 시간복잡도는 O(N) * 10까지 진행될 수 있습니다. 그 이유는 10은 수의 최대 자릿수를 의미하기 때문에 N의 시간복잡도를 넘어버리게 됩니다. 문자열 String은 새로운 객체를 계속해서 생성하기때문에 압도적으로 시간복잡도가 증가하는 경우가 될 수 있습니다.

따라서, 일반적인 브루트포스방법으로는 모든 N까지를 진행하게 되면 시간초과가 나게 됩니다. 그렇기 때문에 다른 방법을 고안할 수 있어야합니다.

다른 방법은 무엇일까?
수학적 연산의 방법을 살펴보면 수의 자리수별로 나누어서 문제를 해결 할 수 있습니다.
만약 N = 120이라고 생각하면

1~9 길이 1
(9-1+1) * 1 
10~99 길이 2
(99-10+1) * 2
100~120 길이 3
(120-100+1) * 3

의 규칙을 찾아낼 수 있습니다. 수의 각 자리별로 나누어서 자리수를 문제를 해결 할 수 있습니다.

결과적으로, (N의자리 최대값 - N자리 최솟값 + 1) * 자리수(N자리수 길이) 으로 자리수를 구할 수 있게됩니다.

1.3. 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/*
자리수 찾기문제
1234567891011 와같이 수를 이어붙이면 브루트포스로 처리하면 O(N) * 10(자리수)의 시간복잡도가 발생하므로 시간초과가 발생합니다.
 */
public class 수이어쓰기1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long ans = 0;
        int len = 1;
        for(int i=1; i<=n; i*=10){
            int j = i*10-1;
            if(j > n){
                j = n;
            }
            ans += (long)(j - i + 1) * len;
            len++;
        }
        System.out.println(ans);

    }
}

AlgorithmBOJ