[Python] 1790 - 수 이어 쓰기 (실버1)

1. 문제 설명

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

1790번: 수 이어 쓰기 2

 

---

2. 아이디어

약간의 수학적 사고력을 필요로 하는 구현 문제다.

이 문제를 정직하게 풀려고 한다면 n만큼 수를 이어붙인 문자열에서 k번째 숫자를 찾아나서야 하는데

최악의 경우가 n == 100,000,000이고 k == 1,000,000,000이다.

데이터 1억개를 처리하는 시간이 대략 1초정도 걸리는데

이걸 다 이어붙이고, 문자열 1억 번째 위치를 찾으려 하면 당연히 타임에러가 발생한다.

 

이런 문제를 해결할 방법을 찾는 가장 좋은 방법은 직접 써보고 패턴을 찾는 것이다.

난 머리가 별로 좋은 편이 아니라서 머릿속으로 암산은 안 될 거 같아 직접 노트에 다 써가면서 했었다.

Scope	Digit	Count	Length (= digit * count)
1 ~ 9	1	9	9
10 ~ 99	2	90	180
100 ~ 999	3	900	2700
1,000 ~ 9,999	4	9000	36000

scope는 자릿수 범위, digit는 자릿수, count는 범위 안에 있는 숫자의 개수,

length는 현재 scope 내의 숫자를 나열했을 때에 차지하는 문자열의 길이이다.

 

가장 처음 digit를 1, count를 9로 잡고 찾고자 하는 위치 k값 보다 작다면,

다음 scope로 이동하여 현재 작업을 반복 수행한다.

여기서 '이동'한다는 개념이 중요하다.

1~9번 인덱스에서 10~99번 인덱스로 이동하였기 때문에 k는 length만큼 계속 마이너스 연산을 해주어야 한다.

반대로 출력시킬 결과 변수에는 count를 플러스 연산해준다.

 

k가 문자열의 길이보다 작아지는 순간 결과를 찾아내어 숫자를 만들어 내야하는데

나는 정작 이 부분에서 한참 막혀있었던 기억이 난다.

 

1234567891011121314151617181920212223242526272829...

예를 들어, 처음 입력받은 k값이 19라면 output은 4가 나와야 한다.

 

위에서 사용한 방법을 썼다면 현재 digit == 2, k==10이 된다. 이 값이 주는 정보를 잘 활용해야 한다.

1~9 scope에서 10~99 scope로 이동했기 때문에 시작 인덱스 또한 "101112..."라고 판단해야 한다.

인덱스라고 했기 때문에 0번째부터 시작해야 하므로 (k-1)에 자릿수만큼 나눈 몫을 구해준다.

그 값에 다시 1을 더해 기존의 count 변수에 더해주면 14라는 값을 얻어낼 수 있다.

(여기가 이해하기가 많이 힘들지만, 직접 해보는 방법 말고는 글로 설명하기가 너무 까다롭다. ㅠㅠ)

 

얻어낸 결과 값이 n보다 크다면 -1을 리턴하면 될 것이고,

정상적으로 출력 가능한 범위 내의 수라면

result를 문자열로 바꾸어 주어 인덱스로 접근해서 값을 얻어내면 된다.

이걸 어떻게 하는데

인덱스 접근이므로 (k-1)은 똑같이 하면 되는데 이번에는 자릿수로 나눈 나머지를 찾는다.

그럼 거기가 바로 14에서 '4'라는 값을 꺼내올 수 있게 된다.

 

아직도 생생하게 떠오르는 고통의 흔적

지금이야 참 쉽죠~? 하고 넘어가지만 당시에는 하루 3문제씩 매일 푸는데 안 풀리는 날엔

독서실에 12시간이 넘도록 쳐박혀서 한 문제만 붙잡고 머리 쥐어뜯은 날도 많다..

---

3. 코드

def solution():
    n, k = map(int, input().split())
    digit = 1
    cnt = 9
    result = 0

    while k > digit * cnt:
        k -= digit * cnt
        result += cnt
        digit += 1
        cnt *= 10
    result += ((k - 1) // digit) + 1
    if result > n:
        print(-1)
    else:
        print(str(result)[(k - 1) % digit])

solution()