[solved.ac 실버3] 1515_수 이어 쓰기 (파이썬, 문자열, 브루트포스)

https://github.com/mangbaam/CodingTest

GitHub - mangbaam/CodingTest: 프로그래머스, 백준 등 코딩테스트 풀이를 기록하는 저장소입니다.

밑의 사진을 클릭하면 문제 링크로 이동합니다

제한 사항

문제

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

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

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

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

입력

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

 

출력

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

예제

00000000000000000000000000000000000000000000000000000000000000000000000

345029834023049820394802334909240982039842039483294792934790209

---

나의 풀이

먼저 문제를 이해해보자.

 

이렇게 미리 만들어놓아야 한다는 뜻은 아니다.

자연수를 차례대로 써보면 위과 같이 된다.

 

만약 입력 받은 수가 1234 라면 1부터 4까지만 쓰면 만들 수 있고 이 경우엔 지워진 숫자가 없는 것이다.

 

입력 받은 수가 234092 라면 1부터 20까지 쓰여야 만들 수 있다.

 

입력 받은 수가 1111111 라면 1부터 14까지 쓰여야 만들 수 있다.

 

이걸 어떻게 할 수 있을까?

1부터 증가하는 자연수를 i라고 하고, 입력 받은 수를 s라고 했을 때 s의 숫자들이 하나씩 나올 때까지 i를 하나씩 증가하면서 찾아야 한다.

 

만약 현재 i가 100이고, s가 23인 상황을 생각해보자.

우선 2를 찾아야 한다. 현재 i는 100인데 2가 없기 때문에 101로 증가한다. 101에도 2가 없기 때문에 102로 증가한다.

1...0.....2 를 찾았다. s에서도 2를 제거해 3으로 만든다.

i를 또 103으로 만들어 탐색한다. 1....0....3 을 찾았다. s에서도 3을 제거하면 s는 더 이상 찾을 숫자가 없게 된다.

찾는 숫자를 모두 찾았다. 그리고 i가 103일 때 모두 찾았기 때문에 103을 출력하면 된다.

 

전체 코드

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

채점 결과