BOJ 30829 부분수열 MEX

먼저 정답의 길이를 구합니다. 정답이 $k$자리이려면 [1-9][0-9]{k-2}는 모두 만들 수 있고 [1-9][0-9]{k-1}은 만들 수 없어야 합니다. 이러한 $k$는 다음의 과정을 거쳐 구할 수 있습니다.

• 맨 뒤에서부터 0부터 9까지를 포함하는 가능한 한 짧은 겹치지 않는 substring들을 찾습니다. 이들의 개수를 $a$라고 합시다.
• 사용되지 않은 글자들이 1부터 9까지를 모두 포함하면 [1-9][0-9]{a}를 모두 만들 수 있으므로 정답의 길이는 $a+2$이고, 그렇지 않으면 $a+1$입니다.

이제 정답은 다음의 과정을 반복하여 구할 수 있습니다.

• 첫 자리의 경우 1부터 9까지, 아닌 경우 0부터 9까지를 순서대로 고려하여 다음의 조건을 충족하지 못하는 가장 작은 숫자 $d$를 그 자리에 적습니다.
  • 현재 자리의 오른쪽에 올 숫자의 개수가 $b$일 때, 남은 문자열에서 가장 처음으로 등장하는 $d$의 뒤에 0부터 9까지를 포함하는 겹치지 않는 substring을 $b$개 만들 수 있습니다.
• 이 조건은 풀이의 앞부분에서 찾은 substring들의 위치를 재활용하여 판별할 수 있습니다.
• 방금 적은 $d$가 처음으로 등장하는 위치까지의 prefix를 문자열에서 모두 제거합니다.