문제
양의 정수를 차례로 이어 씁니다. 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
예시
입력:
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]입니다.
입력:
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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.