BOJ 32789 Champernowne Subsequence

문제 링크:

문제 내용

양의 정수 $k$에 대해, 1부터 $k$까지의 모든 양의 정수를 순서대로 이어 붙여서 얻는 정수를 $k$번째 Champernowne 수라고 합니다.

숫자로만 이루어진 임의의 문자열이 주어질 때, $k$번째 Champernowne 수가 그 문자열을 부분 수열로 갖는 가장 작은 $k$를 구하세요. 그러한 $k$는 항상 존재함을 증명할 수 있습니다.

입력

첫 줄에 문자열의 길이 $n$이 주어지고, 둘째 줄에 숫자로만 이루어진 길이 $n$의 문자열이 주어집니다. ($1 \le n \le 10^5$)

출력

문제의 정답을 출력합니다.

문제 풀이