[BOJ]1790번: 수 이어 쓰기 2 (c++)

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

1790번: 수 이어 쓰기 2

 

이분탐색

#include <iostream>
#include <string>

using namespace std;

// 1부터 N까지 수를 이어붙인 길이 구하기
long long cal_length(int N)
{
	long long len = 0;
	for (int start = 1, i = 1; start <= N; start *= 10, ++i)
	{
		int end = start * 10 - 1;
		if (end > N)
		{
			end = N;
		}

		len += (long long)(end - start + 1) * i;
	}
	return len;
}

int binary_search(int left, int right, int target)
{
	if (left >= right)
	{
		return right;
	}

	int mid = (left + right) / 2;
	long long len = cal_length(mid);

	/*
		1부터 mid까지 이어붙인 수의 길이 < target 이면
		[mid + 1, right] 범위에서 재 탐색
	*/
	if (len < target)
	{
		return binary_search(mid + 1, right, target);
	}
	/*
		1부터 mid까지 이어붙인 수의 길이 >= target 이면
		[left, mid] 범위에서 재 탐색 (mid값 포함)
	*/
	else
	{
		return binary_search(left, mid, target);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	int N, K;
	cin >> N >> K;

	// 수의 길이가 K보다 작은 경우
	if (cal_length(N) < K)
	{
		cout << -1;
		return 0;
	}

	// 1부터 num까지 이어붙였을 때의 길이가 K보다 같거나 큰 최소의 수 num구하기
	int num = binary_search(1, N, K);

	// 1부터 num까지 이어붙였을 때의 길이 num_len구하기
	int num_len = cal_length(num);
	
	string s_num = to_string(num);

	// num에서 뒤에서 (num - K)만큼 앞에 있는 숫자 구하기
	cout << s_num[(s_num.size() - 1 - (num_len - K))];

	return 0;
}

 

 

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

1234567891011121314151617181920212223...

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

 

풀이과정은 다음과 같다.

1. 1부터 num까지 이어붙인 수의 길이 num_len이 K보다 같거나 큰 최소의 수 num을 구한다.

2. num_len과 K의 차이를 구해 K번째 수를 구한다.

 

 

1번 과정에서 이분탐색을 활용한다.

수의 길이를 구할때의 시간복잡도는 O(N의 길이)이고

이분탐색의 시간복잡도가 O(log N)이기 때문에 시간제한에 걸리지 않고 풀이할 수 있다!

 

 

 

이분탐색을 참고한 블로그

이진 탐색과 시간 복잡도 분석 (Binary Search and its Time Complexity Analysis)