[Implementation] 백준 1790번 “수 이어 쓰기 2” Python 풀이

문제 링크

• https://www.acmicpc.net/problem/1790

풀이

• 단순히 문자열을 이어붙이면 메모리초과가 발생합니다.
• 따라서, 각각의 자릿수에 해당하는 숫자의 개수와 각 숫자의 글자수를 활용해 문제를 해결할 수 있습니다.
  • 1의 자리인 숫자는 9개이며, 각 숫자의 글자수는 1개입니다.
  • 10의 자리인 숫자는 90개이며, 각 숫자의 글자수는 2개입니다.
  • 100의 자리인 숫자는 900개이며, 각 숫자의 글자수는 3개입니다.
• 따라서, 원하는 자릿수 K가 200이라면 아래와 같은 방식으로 해당하는 문자를 추측할 수 있습니다.
  • 우선, 200을 넘지 않는 선에서, 1의 자리숫자와 10의 자리숫자가 모두 사용되는 것을 알 수 있습니다.
    • 1 x 9 + 90 x 2 = 189
  • 200 - 189 = 11 이므로, 이제 K까지 남은 칸은 11칸입니다.
  • 1의 자리숫자와 10의 자리숫자를 모두 사용했으므로, 이제 남은 숫자들은 100의 자릿수입니다.
  • 따라서, (11-1)/3의 몫과 나머지를 계산합니다.
  • 몫은 3이며, 이는 100의 자릿수가 사용된 횟수를 의미합니다.
    • 따라서, 103(100 + 3)이 사용되는 순서라는 것을 알 수 있습니다.
  • 나머지는 1이며, 마지막으로 사용된 100의 자릿수에서 몇 번째 숫자인지를 의미합니다.
    • 103을 기준으로 0번째 숫자는 1, 1번째 숫자는 0, 2번째 숫자는 3을 의미하므로,
    • 1번째 숫자는 0인 것을 알 수 있습니다.

코드

import sys

# n까지의 수와 k번째 자리 숫자
n, k = map(int, sys.stdin.readline().split())

# 마지막으로 사용된 숫자
last_num = 0
# 현재 자릿수
num_len = 1
# 현재 자릿수의 모든 숫자의 개수
num_count = 9

# 남은 자릿수가 [현재 자릿수 * 현재 자릿수의 모든 숫자의 개수]보다 크다면
while k > num_len * num_count:

    # 남은 자릿수 업데이트
    k -= num_len * num_count

    # 마지막으로 사용된 숫자
    last_num += num_count

    # 현재 자릿수 증가
    num_len += 1
    # 현재 자릿수의 모든 숫자의 개수 증가
    num_count = num_count*10

# (마지막으로 사용된 숫자 + 1) + (다음 자릿수에서 남은 숫자의 개수)
last_num = (last_num+1) + ((k-1) // num_len)

# 마지막으로 사용된 숫자가 n보다 크다면
if last_num > n:
    print(-1)
else:
    # 나머지를 계산함으로써, 마지막으로 사용된 숫자의 몇번째 숫자인지 확인
    print(str(last_num)[ (k-1) % num_len])

참고

• https://wootool.tistory.com/28