모든 챌린지
보통 0명 해결 정답률 0%

챔퍼나운 수의 자릿수

자연수를 이어 쓴 문자열 123456789101112...에서 주어진 위치의 숫자를 찾습니다.

배우게 될 내용

  • 길이별로 수들이 차지하는 자릿수를 셀 수 있다
  • 위치로부터 해당 수와 숫자를 찾을 수 있다
  • 64비트 연산을 안전하게 사용할 수 있다

문제

원문 보기 (영어)

양의 정수를 차례로 이어 씁니다. 123456789101112131415... 1번 위치에는 1, 10번 위치에는 10의 1, 11번 위치에는 10의 0이 있습니다. 요청받은 각 위치에 어떤 숫자가 있는지 찾으세요. 위치 값이 문자열로 직접 만들 수 있는 범위를 훨씬 넘으므로, 자릿수가 같은 수들의 묶음을 통째로 건너뛰세요(한 자리 수 9개, 두 자리 수 90개, 세 자리 수 900개, ...).

champernowne_digits(positions) 함수를 구현하세요.

입력

positions: 숫자 문자열에서의 위치들이며 1부터 셉니다.

출력

각 위치의 숫자를 입력과 같은 순서로 반환합니다. 입력이 비어 있으면 빈 리스트를 반환합니다.

제약 조건

0 ≤ positions.length ≤ 100; 1 ≤ position ≤ 10^15

예시

예시 1
입력:
positions = [1, 9, 10, 11]

예상 출력:
expected = [1, 9, 1, 0]
입력:
std::vector<long long> positions = {1, 9, 10, 11};

예상 출력:
std::vector<long long> expected = {1, 9, 1, 0};
입력:
long[] positions = new long[] {1, 9, 10, 11};

예상 출력:
long[] expected = new long[] {1, 9, 1, 0};

설명

문자열은 1 2 3 4 5 6 7 8 9 1 0 1 1로 시작하므로 숫자는 [1, 9, 1, 0]입니다.

예시 2
입력:
positions = [15, 190]

예상 출력:
expected = [2, 1]
입력:
std::vector<long long> positions = {15, 190};

예상 출력:
std::vector<long long> expected = {2, 1};
입력:
long[] positions = new long[] {15, 190};

예상 출력:
long[] expected = new long[] {2, 1};

설명

15번 위치는 12의 2입니다. 10번부터 189번 위치까지는 10부터 99까지가 차지하므로 190번은 100의 첫 번째 숫자입니다. 답은 [2, 1]입니다.

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

d자리 수들은 모두 합해 9 × 10^(d − 1) × d개의 위치를 차지합니다.

힌트 2

위치가 어느 묶음 안에 들어올 때까지 묶음 전체를 빼 나가세요.

힌트 3

묶음 안에서 (position − 1) / d는 몇 번째 수인지, (position − 1) % d는 그 수의 몇 번째 숫자인지 알려 줍니다.

예상 복잡도

시간 O(m × log P) (m은 위치의 개수), 추가 공간 O(m)

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.