[백준] #1515 수 이어 쓰기(python)

📌문제

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

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

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

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

입력

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

출력

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

예제 입력1

1234

예제 출력1

1

예제 입력2

234092

예제 출력2

20

백준 1515번 문제

💡Idea

1부터 N까지 이어서 쓴 수에서 일부가 지워졌을 때 N의 최솟값을 구하는 문제입니다.

생각보다 굉장히 단순한 접근으로 풀 수 있는 문제였지만, 접근법 찾기까지 약간 시간이 걸렸던 문제입니다😅

그냥 숫자를 1부터 증가해가며, 쓰여져 있는 숫자 중에서 겹치는 부분이 있는지 확인하는 식으로 문제를 해결하면 됩니다.

1. 숫자 1부터 시작하여, 쓰여져 있는 숫자들을 앞에서부터 같은 부분이 있는지를 확인한다.
   1-1. 숫자가 두 자리 수 이상일 경우, 모든 자릿수의 수들 중에서 같은 부분이 있는지를 확인해야 한다.
   📍 일의 자릿수가 지워져 있을지, 그 이상의 자릿수가 지워져 있을지 알 수 없기 때문
   1-2. 만약 같은 부분이 있다면 쓰여져 있는 다음 숫자로 넘어간다.
   📍 이 때, 다음 숫자로 넘어간다고 무조건 확인하고 있는 숫자가 증가하는 것은 아니다.
2. 위의 과정을 반복한다.

💻코드

• ⏰ 시간 : 56 ms / 메모리 : 31388 KB

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()

📝코드 설명

변수

• n : 현재 쓰여져 있는 숫자들과의 일치 여부를 확인하고 있는 숫자
• idx : 현재 쓰여져 있는 숫자들 중 어느 숫자를 확인하고 있는지를 나타내는 인덱스