난이도

Silver 3

풀이 참고 유무

X

막힌 부분

아이디어

문제

문제 바로가기
세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다.
세준이는 저녁을 먹으러 갔다 와서, 자기가 쓴 수의 일부가 지워져있는 모습을 보고 충격받았다.
세준이는 수를 방금 전과 똑같이 쓰려고 한다. 하지만, N이 기억이 나지 않는다.
남은 수를 이어 붙인 수가 주어질 때, N의 최솟값을 구하는 프로그램을 작성하시오. 아무것도 지우지 않을 수도 있다.)

입력

첫째 줄에 지우고 남은 수를 한 줄로 이어 붙인 수가 주어진다. 이 수는 최대 3,000자리다.

출력

가능한 N 중에 최솟값을 출력한다.

예제 입력

82340329923

예제 출력

43

문제 검토

처음부터 하나씩 찾아가면 될 것 같다.

풀이(python)

Python

s=input()
sidx=0
answer=1
check=False
while True:
    sanswer=str(answer)
    for x in sanswer:
        if s[sidx]==x:
            sidx+=1
            if sidx==len(s):
                check=True
                break
    if check:
        break
    answer+=1
print(answer)

1부터 차례대로 나열한 수 들중 숫자를 몇개 뺀 것이니 내가 수를 1부터 차례대로 나열하면서 나오는대로 기록하면 되는 것이다.

포인터가 끝까지 돌았다면 그것이 가능한 최소이니 그 때 answer를 출력한다.

걸린 시간

29:44

총평

접근을 잘못하고 아이디어가 잘 생각나지 않아 생각보다 어렵게 느껴졌다.
이런 문자열 문제는 항상 시간 부족이 잘 나타나서 완탐을 생각하지 못했는데 문자열이 나오면 완탐을 꼭 고려하자.