1790 수 이어 쓰기2

 

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

1790번: 수 이어 쓰기 2

수 이어 쓰기 2 성공분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

64 MB

3119

831

659

32.495%

문제

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

1234567891011121314151617181920212223...

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

입력

첫째 줄에 N(1 ≤ N ≤ 100,000,000)과,  k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다.

출력

첫째 줄에 앞에서 k번째 자리 숫자를 출력한다. 수의 길이가 k보다 작아서 k번째 자리 숫자가 없는 경우는 -1을 출력한다.

 

 

(풀이)
1. string으로 저 숫자를 모두 받아 인덱스 참조하여 찾으면 시간 초과난다.

2. 따라서, 시간복잡도를 O (log(1억)) 으로 계산하여 값을 점점 좁혀가며 이분 탐색을 해야한다.

 

3. 핵심은 1~N까지 수들 중에

  1~9 (1자리)
  10~99 (2자리)
  100 ~ 999(3자리) 씩 자리수가 변동 되는 부분을 구현과 가운데 추정 값이 찾고자 하는 K번째 와 비교하여
  왼쪽 인지 오른쪽인지 결정하여 탐색하면서 범위를 좁혀가면 된다.

 

4. Left , Right   ,Mid 값을 가지고

 

  (1) Mid 값을 기준으로 글자 길이를 구한다음, 구한 글자 길이가 K보다 작으면

      mid를 기준으로 왼쪽에는 답이 존재하지 않는다고 판단.

 

  (2) 그 반대면 오른쪽에는 존재하지 않는다고 판단하여 mid 값을 좁혀갈수 있다.

 

  (3) 찾은 미드값의 위치는 해당 값의 가장 오른쪽(끝 값이므로 찾고자하는 위치 보정을 다시 또 구현해주어야한다. (41~45번째줄 코드)

 

5. 이 문제는 이분 탐색을 구현하는건 어렵지 않은데, 수학적인 요소들을 고려하는 부분이 어렵다.

 

 

#include<iostream>
#include<string>
using namespace std;
 
int get_length(int n);
void go(int start, int end);
int N, K;

int main(void)
{
	cin >> N >> K;
	if (get_length(N) < K)
	{
		cout << -1 << '\n';
		return 0;
	}
	go(1, N);
	return 0;
}
void go(int start, int end)
{
	int pos;
	while (start <= end)
	{
		int mid = (start + end) / 2;
		int length = get_length(mid);
		
		if (length < K) // 오른쪽
		{
			start = mid + 1;
		}
		else // 왼쪽
		{
			pos = mid;
			end = mid - 1;
		}
		
	}
	//k = 23, pos = 16

	// str[] = {1,6} ,[index = 16] = 6;
	int c = get_length(pos); // c = 23, pos = 16
	string str = to_string(pos); //str.size() - 1 = 0,1,2,3 . .
	// c - k = 0  str의 가장 끝 인덱스
	cout << str[str.size() - 1 - (c - K)] << ' ';
	return;
}
int get_length(int n)
{
	//	1~9 (9-1)+1 * 1
	//	10~99 (99-10)+1 * 2
	//	100~999 (999-100)+1 * 3

	int length = 0;
	for (int start = 1, len = 1; start <= n; start *= 10, len++)
	{
		int end = start * 10 - 1;
		if (end > n)
			end = n;
		
		length += ((end - start) + 1) * len;
	}
	return length;
}