BOJ 1515 - 수 이어 쓰기

문제

1부터 순서대로 이어 쓴 문자열에서 일부 숫자를 지운 결과가 주어질 때, 원래 이어 쓴 마지막 수의 최솟값을 구하라.

입력

지워진 후 남은 숫자 문자열이 주어진다 (길이 1 이상 3000 이하).

출력

마지막 수의 최솟값을 출력한다.

예제

입력	출력
`1234567891`	`10`

풀이

1부터 순서대로 수를 생성하며, 각 수의 자릿수를 입력 문자열과 그리디하게 매칭한다.

n을 1부터 증가시키며 각 수를 문자열로 변환한다
수의 각 자릿수가 입력의 현재 위치와 일치하면 인덱스를 전진시킨다
일치하지 않으면 해당 자릿수는 지워진 것으로 간주하고 건너뛴다
입력의 모든 문자가 매칭되면 현재 n이 답이다

핵심 아이디어: 그리디하게 가장 빠른 매칭을 선택하면 마지막 수가 최소화된다.

코드

import sys
 
nums = sys.stdin.readline().rstrip()
n = 0
idx = 0
while True:
    n += 1
    for s in str(n):
        if nums[idx] == s:
            idx += 1
            if idx >= len(nums):
                print(n)
                exit()

복잡도

시간: O(N * d), N은 답, d는 자릿수
공간: O(1)

문제