알고리즘 :: 백준 :: 이진탐색 :: 파라메트릭 서치 :: 1790 :: 수 이어 쓰기 2

문제

문제 링크

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.
1234567891011121314151617181920212223...
이렇게 만들어진 새로운 수에서, 앞에서 k번째 자리 숫자가 어떤 숫자인지 구하는 프로그램을 작성하시오.

문제접근

• N의 범위가 1억까지, k의 범위가 10억까지이므로 O(log(n)) 풀이를 구상하는 것이 자연스럽다.
• 임의의 수 m까지 나열한 문자열의 길이를 구한 것과 k를 비교하면,
  • m > k 라면 더 작은 m값을 탐색한다.
  • m < k 라면 더 큰 m값을 탐색한다.
• 즉, 이 문제는 넓은 범위의 최적화 문제를 결정 문제로 바꿔야 하는 파라메트릭 서치로 풀어야 한다.

1. left를 1, right을 N이라고 생각했을 때, mid는 N/2이다.
2. mid까지 나열한 문자열 길이 len을 구하고 k와 비교한다.
3. len이 k보다 작다면 left를 mid + 1로 옮겨서 오른쪽 부분을 탐색한다.
4. len이 k보다 크다면 right을 mid - 1로 옮겨서 왼쪽 부분을 탐색한다. 이때, 외부(ans)에 mid값을 기록해둔다.
5. 위 과정을 left와 right이 교차할 때까지 반복한다.
6. 반복문을 빠져나왔을 때, 우리는 4번에서 외부에 저장해놓은 수 ans가 k번째 인덱스가 가리키는 수 임을 알 수 있다.
7. 마지막으로 k번째가 해당 수 ans의 어떤 숫자를 가리키고 있는지 판단한다.
8. ans까지의 길이에서 k를 빼고 1을 더 빼주면 ans의 몇 번 인덱스를 가리키는지 알 수 있다.

코드

#include <cstdio>
#include <cmath>
typedef unsigned long long ull;

// 정수 n의 자릿수를 구하는 함수
int getStand(int n) {
	int ret = 0;
	while (n > 0) n /= 10, ret++;
	return ret;
}
// 정수 n까지 나열했을 때 문자열의 길이
// '수 이어 쓰기 1' 문제의 핵심 알고리즘
ull getLen(int n) {
	int len = getStand(n);
	ull ret = 0;
	while (len > 0) {
		int tmp = n - pow(10, len - 1) + 1;
		ret += tmp * len;
		n -= tmp;
		len--;
	}
	return ret;
}
// 파라매트릭 서치
int solve(int n, int k) {
	ull len = getLen(n);
	if (len < k) return -1;
	
	int l = 1, r = n, m, ans;
	while (l <= r) {
		m = (l + r) / 2;
		len = getLen(m);	
		if (len < k) l = m + 1;
		else ans = m, r = m - 1;
	}
	char buf[11];
	int s = sprintf(buf, "%d", ans);
	len = getLen(ans);
	return buf[s - (len - k) - 1] - '0';
}

int main() {
	int N, k;
	scanf("%d %d", &N, &k);
	printf("%d\n", solve(N, k));
}

결과