[백준][1748번] 수 이어 쓰기1

문제 URL

https://www.acmicpc.net/problem/1748

시간초과 풀이

import java.io.*;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int answer = 0;

        for(int i=1; i<=n; i++){
            answer += Math.log10(i)+1;
        }
        System.out.println(answer);
    }
}

해결한 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int len = (int) (Math.log10(n) + 1);
        int ans = 0;
        int cnt = 10;

        for (int i = 1; i <len; i++) {
            ans += (cnt - cnt/10)*i;
            cnt*=10;
        }

        ans += (n - cnt/10 + 1) * len;

        System.out.println(ans);
    }
}

다른 풀이

import java.util.*;
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long ans = 0;
        for (int start=1, len=1; start<=n; start*=10, len++) {
            int end = start*10-1;
            if (end > n) {]
                end = n;
            }
            ans += (long)(end - start + 1) * len;
        }
        System.out.println(ans);
    }
}

느낀점

브루트 포스를 계산하기전 경우의수를 먼저 계산해서 생각해낸 풀이법이 적절한지 먼저 판단해야한다.

• 시간초과 이유 나의 풀이대로면 시간복잡도는 O(N)이고 문제의 크기는 N<=1억이다. 시간제한 1초에 걸릴 수 밖에 없다. 따라서 O(N)보다 더 효율적인 방법이 필요하다.

• 해결법 N = 120 이라고하자

  1. 1- 9는 1이 중복된다. -> (9-1+1) * 1
  2. 10 -99은 2가 중복된다. -> (99-10+1) * 2
  3. 100 - 120은 3이 중복된다. -> (120-100+1) * 3

최대 9번 더하게 되니까 시간복잡도 : O(N) 으로 해결가능하다.

• 생각의 전환을하면 연산의 횟수를 크게 줄일수있다!