[BOJ] 1515. 수 이어 쓰기

문제:

세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다.

세준이는 저녁을 먹으러 갔다 와서, 자기가 쓴 수의 일부가 지워져있는 모습을 보고 충격받았다.

세준이는 수를 방금 전과 똑같이 쓰려고 한다. 하지만, N이 기억이 나지 않는다.

남은 수를 이어 붙인 수가 주어질 때, N의 최솟값을 구하는 프로그램을 작성하시오. 아무것도 지우지 않을 수도 있다.)

입력:

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

출력:

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

풀이방법:

원래 세준이가 쓴 숫자는 다음과 같을 것이다.

12345678910111213141516....

그래서 앞에서 부터 일치하는 숫자들을 찾고서 더 이상 일치할 숫자를 찾을 수 없을 때까지 반복한다.

 

즉, 234092와 같은 경우에는 1234567891011121314151617181920 중 굵은 숫자의 일부분이 남은 것과 같다. 1부터 하나씩 증가하면서 234092와 비교한다. 2,3,4 에서는 바로 일치되긴 하지만 10부터는 바로 일치되지 않을 것이다. 따라서 자릿수가 늘어난 경우에는 모든 자리에서 일치하는지 여부를 확인하도록 한다.

N = input()
 
i = 0
while True:
    i+=1
    num = str(i)
    while len(num) and len(N):
        if num[0]==N[0]:
            N = N[1:]
        num = num[1:]
    if len(N)==0:
        print(i)
        break

문제링크:

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

1515번: 수 이어 쓰기