[백준] 12755번 수면 장애, 파이썬 문제 풀이

문제

백준 12755번 수면 장애를 극복하기 위해 숫자를 세는데, 숫자를 이어 붙였을때 주어진 N번째 숫자는 무엇인지 찾는 문제를 해결했습니다. 

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

12755번: 수면 장애

문제

수면 장애를 가진 강민이는 잠이 오지 않아 적잖은 고통을 느끼고 있다. 강민이는 잠이 오지 않을 때마다 속으로 양을 세고 있었는데, 오늘따라 백만 마리까지 세었는데도 잠이 오지 않았다.

한계를 느낀 강민이는 새로운 방법으로 수를 세기로 했다.

1부터 숫자를 쭉 이어 붙이면 다음과 같은 숫자열이 생성된다.

12345678910111213...

강민이는 이 숫자열을 한 숫자씩 떼어서 읽기 시작했다. 수면에 성공한 강민이는 다음날 일어나자마자 "N번째 숫자까지 읽었어!" 라고 기분 좋게 외쳤다.

과연 N번째 숫자는 무엇일까?

입력

첫째 줄에 N번째 숫자를 나타내는 N이 주어진다. (1≤N≤100,000,000)

예시: 15

출력

첫째 줄에 N번째 숫자에 해당하는 0~9 중 한 숫자를 출력하시오.

예시 : 2

 

문제 풀이

쉽게 생각하면, 숫자를 문자열로 만들어서 길이가 N 이하일 때까지 이어 붙여서 인덱스로 출력하면 됩니다. 하지만, 이렇게 하면 시간 초과가 발생합니다. N의 범위가 크기 때문입니다. 따라서, 계산 과정을 줄이는 노력을 해야합니다.

 

우선, 주어진 예시를 확인해보도록 하겠습니다. 입력으로 N=15가 주어졌습니다. 숫자를 이어 붙여서 15번째 숫자를 찾으면 다음과 같습니다.

123456789101112

이렇게 2를 찾기 위해서는, 2가지 정보를 알고 있어야 합니다. 첫 번째는 어떤 숫자를 가리키고 있는지 알고 있어야 합니다. 두 번째는 그 숫자의 몇 번째 자릿수인지 알고 있어야 합니다. 가령, N이 가리키고 있는 숫자가 "12"라면, 1인지 2인지 알아야된다는 뜻입니다.

 

숫자를 찾기 위해서 자릿수를 알고 있어야 합니다. 왜냐하면, 각 자릿수마다 숫자의 개수가 달라지기 때문입니다. 그래서 범위를 찾아보면 다음과 같습니다.

 

1자리 : 0 ~ 9 → N=0~9 (주어진 조건은 N>0이긴 합니다.)

2자리 : 10 ~ 99 → N = 10~ 189 

3자리 : 100 ~ 999 → N = 190 ~ 2889

4자리 : 1000 ~ 9999 → N = 2900 ~ 35999

 

각 범위의 최대값을 다시 표현하면 다음과 같습니다.

 

9 = 9*1

189 = 9*10*2-1 

2889 = 9*100*3-1

35999 = 9*1000*4-1

 

조금 더 생각해보면, 10미만은 주어진 N이 답이기 때문에 제외하고 2자리부터 보면 일정 규칙이 보입니다. 각 자릿수만큼 0을 붙여주고, 자릿수를 곱한 뒤, 1을 빼주는 것입니다. 이 규칙을 활용해서 자릿수를 구할 수 있습니다.

 

각 자릿수의 최소값은 N이 몇인지, 그 N이 가리키고 있는 숫자가 무엇인지 알고 있습니다. 이 정보를 활용해서 주어진 N이 최소값으로부터 얼마나 떨어졌는지 알 수 있습니다. 이는, N이 가리키고 있는 숫자가 무엇인지 의미합니다. 또한, 얼마나 떨어졌는지에 대한 값을 자릿수로 모듈러 연산(%)을 하게 되면 N이 가리키고 있는 숫자의 몇 번째 자릿수를 가리키고 있는지 알 수 있습니다. 

 

위 내용을 코드로 표현하면 다음과 같습니다.

N = int(input())

digit = 1
i = 2
j = 1
prev = 9
maximum = 9

if(N<10): # 한 자릿수 숫자는 N과 같다.
    print(N)
    exit(0)

#N은 몇번째 자릿수인지? , 각 자릿수별 최소 범위를 찾아서 찾음, 자릿수별 범위는 이전 최대값~현재 최대값
while(1):
    maximum += 9*(10**j)*i
    if(prev < N and maximum >= N):
        print(i)
        break
    i+=1
    j+=1
    prev=maximum
# i=자릿수 / j=0붙여주기

cnt = (N-(prev+1))//i  # 각 자릿수별 최소숫자(1,10,100)으로부터 몇 번째 숫자인지?
num = (10**(i-1)) + cnt # 그럼 N이 가리키고 있는 숫자는 무엇인지?
num = str(num) # 숫자를 인덱스로 접근하기 위한 캐스팅
d = (N-(prev+1))%i # N은 숫자의 몇 번째인지? -> num=123 이면, 123의 몇번째 숫자인지?
print(num[d]) # 답

 

정리

백준 티어로 실버5 티어 문제로, 쉬워보여서 도전했다가 큰 코 다쳤습니다. 생각보다 오래 걸렸고, 어려움을 느꼈습니다.. 더 많은 공부가 필요한 시점인 것 같습니다..