코딩테스트 스터디-1790 수 이어 쓰기2

ACMICPC 1790 수 이어 쓰기 2

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

>1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수에서, 앞에서 k번째 자리 숫자가 어떤 숫자인지 구하는 프로그램을 작성하시오.

설명

굉장히 해맨 문제였다. GPT의 도움을 받아 겨우 해결할 수 있었는데… 설명하자면 다음과 같다.

• 우선 규칙을 찾아야 한다.
  • 일의 자리는 1에서 9까지, 총 9개이다.
  • 십의 자리는 10에서 99까지, 총 90*2 = 180개이다.
  • 백의 자리도 100에서 999까지 900*3 = 2700개…
  • 따라서 각 자리에 해당되는 수는 (자리수)x9x(몇의자리)가 된다!
• N이 2000, k가 1500이고 가정해 보면
  • 일단 일의 자리는 9개이니까 넘기고, 십의 자리도 180개니까 넘기는데, 백의 자리는 2700개니까 k는 백의 자리에 있을 것이다.
  • 그 다음 k번째 수가 무슨 수인지를 찾으면 된다.
    • 사실 이게 가장 어려웠다. 이거를 어떻게 찾는가 말인가…
    • 우선 백의 자리니까 3개 단위로 수가 나뉜다. 그리고 1500-180-9=1311 이니까 k는 백의 자리에서 1311번째에 해당되는 수일 것이다.
  • 백의 자리니까 100부터 시작할 것이다. 1311-1(일의자리가 0부터 시작하지 않으니까)을 3으로 나눈 몫을 구한다.
    1311/3 는 436…2이니까 3단위로 나눈 수의 436번째에 해당된다. 여기에 100을 더해 주면 536, 따라서 k번째 수는 536에 위치한다!
  • 그 다음에는 마지막으로 이 536에서 몇번째 수인지를 확인해야 한다. 이것도 마찬가지로 1311-1를 3으로 나눈 나머지에 해당될 것이다.
    왜 나머지냐면 보통 순서계산에서 몇 번째인지를 구할 때는 몫, 인덱스를 구할 때는 나머지를 구하니까 말이다…–단순 직감–
    위에서 계산했을 때 나머지는 2였으니까 536의 2번째 인덱스, 즉 6이 되는 것이다!
• 만약 N이 10이고 k가 11이면..
  • 일단 일의자리는 넘었으니까 11-9=2: 십의자리의 2번째
  • 십의자리는 2개 단위로 수가 올라가고 10은 제외해야 하니까 (2-1)/2 = 0…1
  • 10에 0을 더하면 k가 속한 수는 10, 거기에서 1번째 인덱스니까 0, 따라서 0이 된다!
• 만약에 k-1을 안하면 어떻게 될까?
  • 2/2 = 1…0
  • 11의 0번째 인덱스니까 0, 이상하게 된다!

정답

아래는 파이썬으로 작성한 코드~

N, k = int(input().split())


def solution(N, k):
    jari = 1
    count = 9 # (자리수) * 9 * (몇의자리) 에서 9 * (몇의자리)
    sijak = 1 # (자리수) * 9 * (몇의자리) 에서 (자리수)

    # k가 속한 자릿수 구하기
    # 자리에 해당되는 개수만큼 계속 빼면서 안넘어갈 때까지
    while k > jari * count:
        k -= jari * count
        jari += 1 # 자리 순번 올려주고
        sijak += count # 자리에서 시작할 수도 올리기
        count *= 10 # 자리가 올라가니까

    # k번째가 어디 수에 속하는지 구하기
    # 아까도 말했듯이 k가 아닌 k-1인 이유는 다른 자리는 다 0부터 시작하는데 일의 자리는 1부터 시작하니까
    number = sijak + (k - 1) // jari
    if number > N:
        return -1

    # 해당 수에서 인덱스 추출
    index = (k - 1) % jari
    return int(str(number)[index])

print(solution(n))       

후기

지금까지 푼 문제들 중 인상깊은 문제라 올려보았다.
아직도 왜 k가 아닌 k-1인지 정확하게 모르겠다…