[자바] 백준 11170 - 0의 개수 (boj java)

문제 : boj11170

 

  최악의 경우가 N=0, M=1,000,000 일 경우이다. 이 때 0부터 1000000까지 하나씩 전부 0의 개수를 확인하더라도 O(1000000*8) 이면 된다(8은 자리수의 최대치). 따라서 그냥 N부터 M까지 하나씩 증가시켜보면서, 10으로 나눠가면서 1의자리가 0인 경우를 직접 세주면 된다!

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (tc-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int cnt = n==0?1:0;
            for (int i = n; i <= m; i++) {
                int tmp = i;
                while (tmp!=0) {
                    if (tmp%10==0) cnt++;
                    tmp/=10;
                }
            }
            sb.append(cnt).append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}