[백준/Python] 1515번 수 이어 쓰기

문제

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

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

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

입력

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

출력

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

문제 풀이

1. number를 1씩 증가시키면서 모든 숫자를 검사한다.(브루트포스)

2. 이 코드에서는 n[idx]와 num이 일치할 때마다 idx를 증가시키는 방식으로 최선의 선택을 한다. (그리디)

3. python에서 for 루프나 while 루프에 else 절을 사용하면, 루프가 완전히 실행된 후 (즉, 루프를 중단하지 않고 정상적으로 종료된 후)에 else 절이 실행되는데 막상 그렇게 써 본 적은 없었다. 그래서 gpt한테 물어봤음.

   
   처음엔 문제를 이해 못해서 풀이과정 올린 블로그를 보고 이해했다. 문자열 n과 num을 비교하여 해결한다. idx가 n의 길이보다 커질 때 해당 수를 출력하면 number의 최솟값을 구할 수 있다.
    

   # n = 234092를 예로 들어보자. n의 길이는 6.
   # 1. number = 0, idx = 0
   # 2. number = 1, idx = 0, n[idx] = 2, num = 1, 1 != 2, continue
   # 3. number = 2, idx = 0, n[idx] = 2, num = 2, 2 == 2, idx = 1
   # 4. number = 3, idx = 1, n[idx] = 3, num = 3, 3 == 3, idx = 2
   # 5. number = 4, idx = 2, n[idx] = 4, num = 4, 4 == 4, idx = 3
   # 6. number = 5, idx = 3, n[idx] = 0, num = 5, 5 != 0, continue
   # 이런 식으로 진행되다가 idx가 n의 길이보다 커지면 해당 수를 출력하고 반복문을 빠져나온다