[백준] B11170

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

11170번: 0의 개수

# 아이디어

n부터 m까지의 숫자의 0의 개수를 찾자. (0 <= n <= m <= 1,000,000)

단순히 m과 n사이의 0의 수를 계산하려면 어렵다. 따라서, m까지의 0의 수 - n까지의 0의 수로 출력값을 계산하자.

만약 n이 0을 포함하는 값이면 출력 결과를 계산할 때 n의 0의 개수만큼 더해주면 된다.

만약 m이 0을 포함하지 않는 값이면 가장 가까운 0을 가지는 작은 값으로 변환하여 계산한다.

 

=> 규칙 구하기

한 자릿수 = 1 -> 1

0,1,2,3,4,5,6,7,8,9

두 자릿수 = 9* 1 -> 9

10,11,12,13,14,15,16,17,18,19

20,21,22,23,24,25,26,27,28,29

...

90,91,92,93,94,95,96,97,98,99

세 자릿수 = 9* ( (2+1*9) + 1*9) ) -> 180

100,101,102,103,104,105,106,107,108,109

110,111,112,113,114,115,116,117,118,119

120,121,122,123,124,125,126,127,128,129

...

190,191,192,193,194,195,196,197,198,199

 

200,201,202,203,204,205,206,207,208,209

210

220

290

네 자릿수 = 9* ( {1* (3+2*9 + 9*(2+1*9))} + {9* ((2+1*9) + 1*9)} ) -> 2052

1000,1001,1002,1003,1004,1005,1006,1007,1008,1009

1010,1011,1012,1013,1014,1015,1016,1017,1018,1019

1020

...

1090

1100,1101,1102,1103,1104,1105,1106,1107,1108,1109

1110,1111,1112,1113,1114,1115,1116,1117,1118,1119

1120

...

1190,...,1199

1200

1900

 

2000

다섯 자릿수 = 9* (31 + 21*9) + 9*2052

10000,10001,10002,10003,10004,10005,10006,10007,10008,10009

10010,10011,10012,10013,10014,10015,10016,10017,10018,10019

10020

10090

10100,10101,

...

11000,11001,

11010

 

20000

※ 0의 개수 규칙:

11, 21, 31, 41, ... 순으로 첫번째 줄의 0의 개수이다.

자릿수 하나가 늘어난 0의 개수는 1개의 새로운 값과 9개의 이전의 값을 더하면 된다. (세 자릿수 이상일 때)

 

### 블로그 참조 (규칙 도저히 못찾겠다;;;;)

n과 m의 범위가 다음과 같기 때문에 일일히 직접 계산해준다. (0 <= n <= m <= 1,000,000)

 

	public static int countZero(int start, int last) {
		int cnt = 0;
		for (int i = start; i <= last; i++) {
			int current = i;
			if (current == 0)
				cnt++;

			while (current >= 1) {
				if (current % 10 == 0) {
					cnt++;
				}
				current /= 10;
			}
		}

		return cnt;
	}

항상 일의 자리만 보고 0인지 아닌지 판별하여 cnt를 늘려주고

이후에 10으로 나눈값을 다시 반복적으로 판별한다.

current에서 가장 높은 자릿수를 판별한 뒤 10으로 나누면 항상 그 값은 0이기 때문에 while문을 탈출한다.

 

💢💢💢

10으로 /연산하고 *연산으로 13 -> 10, 29->20으로 만들어 10과 20까지의 0의 개수를 구하자는 생각을 했었는데, 정작 0의 개수를 어떻게 구할지는 생각을 하지 않았다. 0의 개수가 나타나는 규칙을 찾는 생각에 매몰되어 생각을 넓게 하지 못했다.

 

# 오답

- 런타임 에러 발생

	public static int countZero(int start, int last) {
		int cnt = 0;
		for (int i = start; i <= last; i++) {
			int current = i;
			if (current == 0)
				cnt++;

			while (current >= 1) {
				if (current % 10 == 0) {
					cnt++;
				}
				current /= 10;
			}
		}

		return cnt;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int testCase = sc.nextInt();
		int[] n = new int[3];
		int[] m = new int[3];
		int[] cnt = { 0, 0, 0 };

		for (int i = 0; i < testCase; i++) {
			n[i] = sc.nextInt();
			m[i] = sc.nextInt();

			cnt[i] = countZero(n[i], m[i]);
		}

		for (int i = 0; i < cnt.length; i++) {
			System.out.println(cnt[i]);
		}

		sc.close();

	}

 

Sol1.

Scanner에서 BufferedReader, StringBuilder 사용하는 것으로 변경

package baekjoon;

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

public class B11170 {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int testCase = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < testCase; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

			int cnt = 0;
			for (int j = n; j <= m; j++) {
				int current = j;
				if (current == 0)
					cnt++;

				while (current >= 1) {
					if (current % 10 == 0) {
						cnt++;
					}
					current /= 10;
				}
			}
			sb.append(cnt).append("\n");
		}
		System.out.println(sb);

	}

}

 

💯💯💯

StringBuilder를 사용하여 .append("\n")를 이용하면 여러가지 값을 하나로 묶어서 출력할 수 있다.

=> 배열 메모리 낭비와 for문 반복을 줄일 수 있다.