https://www.acmicpc.net/problem/1019
1019번 문제는 설명이 짧아서 간단할 것 같았는데 정답률(이 글을 쓸 땐 36%네요.)을 보고 뭔가 있군... 했던 문제입니다. 문제는 첫 페이지가 1쪽이고 마지막 페이지가 N쪽인 책에서 0~9까지 각 숫자가 몇번 등장할 것인지 출력하는 것입니다. 간단하지만... 간단하진 않습니다. 입력받을 수 있는 수가 최대 10억이기 때문이죠. 입력받은 수를 그대로 반복문을 돌려 각 자리 숫자를 센다면, 꼼짝 못하고 시간초과를 받을 수 있는 문제입니다.
문제에서는 11이 예시로 들어져 있는데요, 11쪽까지 있는 책의 페이지는 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 이렇게 이루어져있고, 1은 총 4번, 나머지 숫자들은 모두 1번씩 등장한다는 것을 알 수 있습니다. 그래서 답은 1 4 1 1 1 1 1 1 1 1 이 되는 것이지요.
Hint!
그대로 반복문을 돌릴 수 없다면, 규칙을 찾아야 할텐데요, 제가 생각해낸 규칙이 설명하기 조금 복잡할 수 있습니다. 그래서 예시를 들어가면서 설명을 하려고 합니다. (그래도 잘 설명이 될지는 자신이 없네요...ㅎ)
먼저, 기본적으로 사용되는 규칙은 첫 페이지의 일의 자리 숫자가 0이고 끝 페이지의 일의 자리 숫자가 9인 경우에서 확인할 수 있습니다. 예를 들어, 20쪽이 첫 페이지이고 69쪽이 마지막 페이지인 책은 1의 자리에서 등장하는 0~9는 각각 5번씩 등장하게 된다는 점이죠. 즉, 일의 자리 숫자가 0이고 끝 페이지의 일의 자리 숫자가 9인 경우 0~9까지 숫자를 일관된 값으로 더할 수 있죠. 그리고 더해지는 값은 첫 페이지와 끝 페이지를 각각 10으로 나눈 몫의 차이에서 1을 더한 값입니다.
20 ~ 69 -> 0~9까지 숫자들이 각각 등장하는 수 = (6-2) + 1 = 5
그리고, 십의 자리에서도 숫자가 등장하는데 2부터 6까지 숫자가 10번씩 등장하게 될겁니다. 즉, 이 경우 답은
5 5 5+10 5+10 5+10 5+10 5 5 5 5, 그니까
5 5 15 15 15 15 5 5 5 가 답이 될겁니다.
이런 아이디어로 출발을 하게 되는데, 여기서 20을 0으로 대체하기만 하면 주어진 문제와 상황이 비슷하게 됩니다. 문제는 페이지가 1부터 시작하게 되니 편의상 0에서 시작한다고 치고 마지막 답에 0의 개수를 하나 빼주면 되겠군요. 그런데 항상 끝 페이지의 일의 자리가 9라는 보장이 없죠? 만약 56 같은 숫자가 주어지면 어떻게 할까요? 이 경우에는 우리가 임의로 56을 59로 변경한 뒤, 위와 같이 계산을 해주고 나머지 57, 58, 59에 존재하는 숫자들을 제외해 주었습니다. 1부터 56까지 등장하는 0~9 숫자를 계산해보도록 할게요.
1. 첫번째 페이지를 0으로, 56을 59로 변경해 먼저 세 줍니다. 이 때, 59와 56의 차이인 3을 미리 계산해 둡니다.
2. 0~59까지 일의 자리에서 등장하는 0~9까지 숫자는 (5-0)+1 = 6 번입니다. 0~9까지 숫자가 등장하는 수에 6을 각각 더해줍니다.
6 6 6 6 6 6 6 6 6 6
3. 59와 56의 차이는 3이므로 9에서 시작해서 내림차순으로 3번째 있는 숫자까지 하나씩 빼줍니다. 즉, 9, 8, 7의 숫자를 하나씩 빼줍니다. 또, 이 세 개의 숫자가 등장하지 않음으로써 십의 자리에 있는 5가 3번 덜 등장하므로, 5의 등장 횟수도 3을 빼줍니다.
6 6 6 6 6 3 6 5 5 5
4. 십의 자리에 등장하는 숫자들을 생각해줍니다. 0~59까지 1부터 5까지 숫자가 총 10번씩 등장하니 더해줍니다.
6 16 16 16 16 13 6 5 5 5
5. 마지막으로, 페이지는 사실 1페이지부터 시작하므로 0의 개수를 하나 제외해줍니다.
5 16 16 16 16 13 6 5 5 5
이렇게 구해낼 수가 있어요. 두 자리까지는 그러려니 하는데, 세 자리 이상엔 어떻게 해야할까요? 세자리 이상에서는 끝에 자리를 하나씩 지워가면서 두자리 수에서 했던 일을 반복해서 진행하면 됩니다. 이건 예시를 드는 것이 이해가 잘 될거에요. 1부터 543까지 등장하는 0~9 숫자를 계산해보며 이해해 보겠습니다.
1. 첫번째 페이지를 0으로, 543을 549로 변경합니다. 이 때, 549와 643의 차이인 6을 미리 계산해 둡니다.
2. 0~549까지 등장하는 0~9까지 숫자는 (54-0)+1 = 55 번입니다. 0~9까지 숫자가 등장하는 수에 55를 각각 더해줍니다.
55 55 55 55 55 55 55 55 55 55
3. 549와 543의 차이는 6이므로 9에서 시작해서 내림차순으로 6번째 있는 숫자까지 하나씩 빼줍니다. 즉, 9, 8, 7, 6, 5, 4의 숫자를 하나씩 빼줍니다. 추가로, 이 6개의 숫자가 등장하지 않음으로써 십의 자리에 있는 4가 6번, 백의 자리에 있는 5가 6번 덜 등장하므로, 각각 빼줍니다.
55 55 55 55 48 48 54 54 54 54
4. 십의 자리에 등장하는 숫자들을 생각해줍니다. 여기가 중요합니다. 십의 자리에 등장하는 숫자들은 백의 자리의 숫자에 따라 각각 고정적으로 몇번씩 등장하는지 결정이 됩니다. 543에서 일의 자리인 9을 없는셈 치면 54입니다. 0에서 54까지 등장하는 0~9의 숫자가 등장하는 수를 생각하면, 십의 자리에 0~9가 몇번 등장하는 지 일의 자리에서처럼 계산할 수 있습니다. 54를 59로 변경하고, 그 차이인 5를 미리 계산해둡니다.
5. 0~59까지 0~9는 (5-0)+1 = 6번씩 등장하게 됩니다. 여기서, 등장하는 0~9는 모두 십의 자리고 각각 10번씩 등장하기 때문에 0~9 숫자가 총 6 * 10 = 60번 등장한다고 할 수 있습니다. 각 숫자의 등장횟수에 60을 더해줍니다.
115 115 115 115 108 108 114 114 114 114
6. 백의 자리가 없는 동안 10의 자리에 0이 등장하는 경우가 10번 덜 등장하므로 0의 등장 횟수에 10을 빼 줍니다.
105 115 115 115 108 108 114 114 114 114
7. 십의 자리 역시 59까지가 아닌 54까지만 등장하였습니다. 그 차이가 5이므로 9에서 시작해서 내림차순으로 5번째 있는 숫자까지 10개씩 빼줍니다. 추가로, 백의 자리 숫자인 5도 5 * 10개씩 덜 등장하므로, 5의 등장 횟수에 그만큼 빼줍니다.
105 115 115 115 108 48 104 104 104 104
8. 백의 자리는 5입니다. 백의자리에서 1~5까지의 숫자에 100씩 더해줍니다.
105 215 215 215 208 148 104 104 104 104
9. 마지막으로, 페이지는 사실 1페이지부터 시작하므로 0의 개수를 하나 제외해줍니다.
104 215 215 215 208 148 104 104 104 104
이 아이디어를 일반화 하여 코드를 짜서 성공하였습니다. 예시에서 일의 자리를 9로 만들어 먼저 등장횟수를 고정적으로 더해주고, 원래 경우와의 차이를 빼주는 것을 자릿수 만큼 반복하여 일반화할 수 있었습니다. 개인적으로, 1로 초기화된 weight 변수를 루프가 돌 때마다 10을 곱하여 각 루프 내에서 활용을 하고 입력받은 숫자인 N을 루프가 끝날 때마다 10으로 나눈 몫(N //= 10)으로 할당하는 것이 코드를 간단히 만드는데 주역을 했다고 생각을 합니다. 또, 세 자리 예시에서 6번과 9번 처럼 0의 개수를 빼주는 작업이 있는데, 3자리 수이면 10의 자리의 0을 10개 1의 자리의 0을 1개를 빼주듯이 4자리 수면 100의 자리에서 0을 100개를 추가로 빼주면 됩니다. 이 규칙을 그대로 루프 내에 녹여낼 수 있었고, 코드를 보면 이해가 가실거에요!
아래의 코드로 성공하였습니다.
import sys
N = int(sys.stdin.readline().replace("\n", ""))
counts = [0 for _ in range(10)]
weight = 1
for step in range(len(str(N))):
replaced = int(str(N // 10) + "9")
remaining = replaced - N
for i in range(len(counts)): counts[i] += (N // 10 + 1) * weight
for i in range(10-remaining, 10): counts[i] -= weight
for number in list(str(N)[:-1]):
number = int(number)
counts[number] -= remaining * weight
counts[0] -= weight
N //= 10
weight *= 10
print(' '.join(map(str, counts)))
'Python > 백준 알고리즘' 카테고리의 다른 글
| [백준 알고리즘: python 3] #1022 - 소용돌이 예쁘게 출력하기 (3) | 2020.01.19 |
|---|---|
| [백준 알고리즘: python 3] #1021 - 회전하는 큐 (0) | 2020.01.17 |
| [백준 알고리즘: python 3] #1018 - 체스판 다시 칠하기 (0) | 2020.01.15 |
| [백준 알고리즘: python 3] #1017 - 소수 쌍 (1) | 2020.01.14 |
| [백준 알고리즘: python 3] #1014 - 컨닝 (2) | 2020.01.13 |
