문제

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

나의 코드

"""
1. 아이디어


2. 시간복잡도

"""

from sys import stdin
input = stdin.readline

# 백준 1748 수 이어 쓰기 1 문제를 함수로 바꾼 것임.
def search_strlen(num): # 1부터 num까지의 자릿수를 구하는 함수.

    length = len(str(num))
    res = 0 # res는 i부터 num까지의 자릿수를 담는 변수.

    for i in range(1, length):
        res += i * (pow(10, i) - pow(10, i - 1))

    res += length * (num - pow(10, length - 1) + 1)

    return res

def bisect():
    left, right = 1, n # left와 right를 각각 1과 입력받은 n으로 설정.

	# 만약 1부터 n까지의 자릿수가 구하고자 하는 k보다 작다면 -1을 리턴한다.
    # k번째 자릿수는 없는 것이므로 이분탐색을 진행할 필요가 없음.
    if search_strlen(n) < k: 
        return -1

    while left <= right:
        mid = (left + right) // 2

        # one_mid는 1부터 mid까지의 자릿수를 담는 변수.
        one_mid = search_strlen(mid)
        
        if one_mid < k: # one_mid가 k보다 작다면 left를 이동해서 오른쪽 부분 탐색.
            left = mid + 1
        else: # one_mid가 k보다 크거나 같다면 right를 이동해서 왼쪽 부분 탐색.
            right = mid - 1
            ans = mid

    return ans

n, k = map(int, input().split())
ans = bisect()

if ans == -1:
    print(-1)
else:
	""" 이때 ans에는 k번째 숫자가 가리키고 있는 숫자가 담겨져 있다.
    
    예제 1과 같이 k = 23일때 ans에는 16이 담겨져 있는데 
    1부터 ans까지의 자릿수 - 구하고자 하는 k + 1을 해주면 idx=1이 반환된다.
    그래서 ans[-idx]을 해주면 6의 값이 출력된다.
    (-idx가 아닌 idx를 해도 6이 나오긴 하지만 세자릿수에서 틀림)
    
    세자릿수인 경우는 밑의 설명 참조.
    """
    idx = search_strlen(ans) - k + 1
    ans = str(ans)
    print(int(ans[-idx]))

    

느낀점

만약 1부터 구하고자 하는 세자릿수 까지의 자릿수가 100이라고 가정해보자.
(터무니없이 작은 숫자 이긴 하지만 쉽게 예시를 들기 위해)

이때, k는 만약 99번째 수를 찾고자 하는 경우라면 위의 공식과 같이
1부터 세자릿수 까지 자릿수 - 구하고자 하는 k + 1 = 2를 반환한다.

k가 만약 98번째 수를 찾고자 하는 경우라면 공식에 의해 3을 반환한다.
k가 만약 100번째 수를 찾고자 하는 경우라면 공식에 의해 1을 반환한다.

그래서 인덱스에 -를 붙여 뒤에서 부터 출력하도록 해야 한다.