문제
세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다.
세준이는 저녁을 먹으러 갔다 와서, 자기가 쓴 수의 일부가 지워져있는 모습을 보고 충격받았다.
세준이는 수를 방금 전과 똑같이 쓰려고 한다. 하지만, N이 기억이 나지 않는다.
남은 수를 이어 붙인 수가 주어질 때, N의 최솟값을 구하는 프로그램을 작성하시오. 아무것도 지우지 않을 수도 있다.)
입력
첫째 줄에 지우고 남은 수를 한 줄로 이어 붙인 수가 주어진다. 이 수는 최대 3,000자리다.
출력
가능한 N 중에 최솟값을 출력한다.
내가 느낀 난이도
풀이가 어려운 것은 아니지만 어떻게 풀지에 대해 생각하느라 어려웠다. 처음에는 1~9까지의 개수를 세어서 해결하려고 했지만 잘 구현되지 않았고, 오답을 출력했다.
더 고민하는 것보단 풀이를 참고하는 게 나을 것 같아서 그렇게 하였다.
-> 참고한 블로그
https://velog.io/@jckim22
나는 20 -> 2 또는 0으로 지워진 경우는 어떻게 처리해야 하나 고민이 많았는데, 참고한 블로그 처럼 수를 하나씩 증가시키면서 그 수의 요소가 포함되어있으면 index를 하나 증가시키는 방식으로 해결할 수 있었다.
코드
# 수 이어 쓰기
# 완전 탐색?
import sys
num = sys.stdin.readline().rstrip()
index = 0
result = 1
check = False
while True:
s = str(result)
for i in s:
if num[index] == i:
index += 1
if index == len(num):
check = True
break
if check:
break
result += 1
print(result)신기했던 것은 완전탐색으로 구현하여도 시간 초과가 발생하지 않았다는 점이다.
아무래도 조건에 수가 최대 3000자리라고 명시되어있기 때문인 것 같다.
조건을 잘 생각해보고, 그리 큰 수가 아니라면 완전탐색도 생각해보는 것이 좋을 것 같다.
