백준 - 0의 개수(java)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/11170

[문제 설명]

N부터 M까지 숫자를 쭈욱 썼을 때 0의 총 개수

100,115이면

101,102,103,...,110,111,112,113,114,115

 

[접근 방법]

규칙이 있어보이지만, 시작 번호가 주어졌다는 점에서 코드가 복잡해질 느낌이 들었다.

그래서 완전 탐색 돌렸다.

숫자는 최대 7자리수이므로 한 숫자에 최대 7번 반복.

테스트 케이스 개수*숫자의 자리수*첫번째숫자부터 끝번 숫자까지 횟수

T*7*(M-N+1) => O(TM)

대략 최대 횟수 연산을 계산해보면 20*7*1,000,000 =>1.4억

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cntOfTestcases = Integer.parseInt(br.readLine());

        for (int i = 1; i <= cntOfTestcases; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int startNumber = Integer.parseInt(st.nextToken());
            int endNumber = Integer.parseInt(st.nextToken());
            int cntOfZero = 0;
	
            for (int number = startNumber; number <= endNumber; number++) {
                int tempNumber = number;
                do {
                    if (tempNumber % 10 == 0) {
                        cntOfZero++;
                    }
                    tempNumber /= 10;
                } while (tempNumber > 0);
            }
            System.out.println(cntOfZero);
        }
    }
}

 

[파이썬 엄청 느림]

T = int(input())
for i in range(T):
    startNumber, endNumber = map(int,input().split())
    cntOfZero = 0
    for j in range(startNumber, endNumber+1):
        while True:
            if j % 10 == 0:
                cntOfZero = cntOfZero+1
            j = j // 10
            if j == 0: break
    print(cntOfZero)

[느낀 점]

요즘 실버가 잘 풀려서 골드를 도전했다가 이상하게 막혀서 다시 쉬운 문제를 풀고 있다.

이런 문제는 깔끔하게 정리해서 한 번에 코드를 짤 정도는 되어야 골드에서 잘 안막히는 느낌이다.

열심히 하자.