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

> 파이썬, 구현, 그리디 알고리즘, 문자열, 브루트포스 알고리즘

 

 

 

📖 문제 : 수 이어쓰기 (Python) 

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

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

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

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

 

 

입력

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

 

 

출력

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

 

 

 

예제 입력 1 

1234

 

 

예제 출력 1

4

 

 

 

내 코드

numbers = list(map(int, input()))
temp, idx = 0, 0
while idx < len(numbers):
    temp += 1
    temp_str = str(temp)
    if str(numbers[idx]) in temp_str:
        for i in range(len(temp_str)):
            if str(numbers[idx]) == temp_str[i]:
                idx += 1
                if idx == len(numbers):
                    break
print(temp)

 

 

 

Point ! ⭐️ 

• 여기서 포인트는 수(temp) 를 1부터 계속 +1씩 하면서 입력된 수가 수(temp)에 있는지를 판단 후, 입력된 수를 계속 읽어가는 것인데요(idx+하면서, idx값이 수가 들어있는 리스트 numbers의 길이보다 작을 때까지 반복)
  
  가능한 N 중에 최솟값을 출력하는 만큼
  만약 수(temp) 가 11일 때 입력된 수가 1과 그 다음수도 1인 경우 하나의 temp에 2개 또는 여러개의 입력된 수를 없앨 수 있으므로,
  하나의 N값에 몇 개의 수를 없앨 수 있는지 또한 판단해야합니다. 

 

 

 

 

 

백준

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

1515번: 수 이어 쓰기