[GoLang] 백준 1019번, 책 페이지

🔍 문제 톺아보기

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

1,000,000,000보다 작거나 같은 N이 주어질 때 
1 ~ N까지의 페이지 번호에서 0~9가 몇 번 나오는지 구해보자

 

백준에서는 1초당 1억을 넘어가면 시간초과를 하게 됩니다

하지만 문제는 10억이기에 당연히 반복문으로 모든 경우의 수를 체크하는 방법은 시간초과가 발생합니다.

 

🔍규칙 찾기

시간초과가 발생함은 곧 규칙이 있고 이거를 찾으면 해결할 수 있다는 의미죠

저 10억 자리의 수를 무언가 하려면 수로 접근하는 게 아닌 문자열로 접근해야 합니다

 

다가가기 1

일단 1부터 99는 구할 수 있을까?

💡어디 보자 십의 자리만 두고 생각하면 1~9가 10번 반복되고 (각 십의 자릿수는 일자리가 9까지 돌기 때문에)

일의 자리는 1부터 시작하니깐 0은 9번 나머지가 10번 반복되네

 

다가가기 2

1 ~ 99는 쉬운데 그러면 1 ~ 56은? 중간까지는 어떻게 구하지?

💡 이번엔 십의 자리는 최대 숫자를 99를 기준으로 생각하면 십의자리끼리의 차인 9 - 5 +1 = 5만큼은 10번씩 반복되지만

5의 경우 6까지만 반복되네 그러면 9-6을 한 3을 빼야지 반복되는 값이 나오겠어

 

일의 자리는 50/10으로 십의 자릿수를 10으로 나눈 후 + 1을 한 값만큼 0~9가 반복되네

하지만 0은 1부터 시작하는 조건 때문에 1을 빼고 7,8,9도 일의 자릿 수가 6이니 하나씩 반복되는 횟수를 줄여야겠네

 

다가가기 3

십의 자리까지 구했다면 이를 백의 자리 이상의 수도 커버할 수 있게 기능을 추가해야 합니다.

맨 왼쪽 수를 제거하고 이를 기준으로 십의 자릿수 프로세스를 반복하는 거죠

대신 아래 기능이 추가되어야 합니다.

• 가장 왼쪽 수 값이 9와 비교했을 때 차감되는 로직을 십의 자릿수 이상에도 적용해야 합니다
• 가장 왼쪽 수를 버리면서 자릿수만큼의 곱셈을 해줄 로직이 필요합니다.

 

이를 만족하기 위해서 아래 프로세스대로 진행합니다

1. 숫자의 길이만큼 반복하는 반복문 안에서 
2. 가장 오른쪽 수를 일의 자리로 가정하고 이를 9로 만든 후 이에 대한 차를 구합니다
3. 일단 일의 자릿 수가 최대로 나오는 수를 정합니다 (ex : 543이면 54+1로 저장하기)
4. 일의 자릿수가 2번에서 구한 차보다 더 나온 값을 제거합니다
5. 일의 자릿수를 제외한 나머지 수에서도 추가로 나온 값을 제거합니다 
6. 1부터 시작하므로 0을 뺍니다 (십의 자릿수, 백의 자릿수도 0부터 시작하지 못하므로 각 자릿수도 뺍니다)
7. 반복문이 진행될수록 page 값과 weight (자릿수) 값을 수정해서 왼쪽 수를 제거하고 자릿수를 늘려 계산합니다.

 

🔍 코드 짜보기

계산 상 편의를 위해 일의 자릿수를 9로 가정한 후 최대 값을 저장한 후 

초과한 자릿수는 빼는 방식으로 진행했습니다.

package main

import (
	"fmt"
	"strconv"
)

func main() {
	var page int
	var page_count int
	counts := make([]int, 10)
	weight := 1

	fmt.Scanln(&page)

	// 입력 값을 문자열로 바꿔서 자릿수 만큼 반복하게 수정
	page_count = len(strconv.Itoa(page))

	for i := 0; i < page_count; i++ {
		// 현재 page 값을 기준으로 1의 자리수를 9로 만들고
		var replaced, _ = strconv.Atoi(strconv.Itoa(page/10) + "9")
		// 차를 구함
		var remaining = replaced - page

		// 일의 자리수 0~9가 나오는 최대 반복 회수 저장
		for index, _ := range counts {
			counts[index] += (replaced/10 + 1) * weight
		}

		// 일의 자리수의 반복수가 초과된 만큼 빼기
		for i := 10 - remaining; i < 10; i++ {
			counts[i] -= weight
		}

		// 일의 자리수를 제외한 나머지 자릿수에서 일의 자릿수가 반복되지
		// 않아서 생기는 수 만큼 뺴기
		strNum := strconv.Itoa(page)[:len(strconv.Itoa(page))-1]
		for _, value := range strNum {
			counts[int(value-'0')] -= weight * remaining
		}

		// 수는 1부터 시작하므로
		// 0이 자릿수만큼 반복되는 경우는 없음 (십의 자리, 백의 자리 이상도 마찬가지)
		counts[0] -= weight

		// 페이지를 줄이고
		page /= 10
		// 자릿수를 증가 시킴
		weight *= 10
	}

	for index, count := range counts {
		if index == len(counts)-1 {
			fmt.Printf("%d", count)
			break
		}
		fmt.Printf("%d ", count)
	}
}