[알고리즘] 백준 1515번: 수 이어 쓰기

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

1515번: 수 이어 쓰기

 

📝 문제

세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다.
그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다.
세준이는 저녁을 먹으러 갔다 와서, 자기가 쓴 수의 일부가 지워져있는 모습을 보고 충격받았다.
세준이는 수를 방금 전과 똑같이 쓰려고 한다. 하지만, N이 기억이 나지 않는다.
남은 수를 이어 붙인 수가 주어질 때, N의 최솟값을 구하는 프로그램을 작성하시오. 아무것도 지우지 않을 수도 있다.)

 

⌨️ 입력

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

 

🖥️ 출력

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

 

💡 아이디어

원루프로 푸는 방법이 머릿속에 그려지지 않는다. 어렵다
일단 반복을 돌며 자릿수가 높은 순서대로 반복하고
for 자릿수와 숫자가 일단 일치하면 자릿수를 거기까지 인덱싱해서 집어넣고 continue
else 이전 수보다 작거나 같으면 10의 단위 하나 높이고 스택에 push
잘 될까...
...
어떻게 해도 방법이 나오지 않아서 그냥 Brute하게 하기로 하였다.

1. 반복문 편의상 res는 0부터 시작한다
2. 현재 nums의 어디까지 비교했는지 기록하기 위해 idx 변수를 생성한다.
3. res에 1씩 반복적으로 더해간다.
4. 자릿수 별로 반복문을 돌리기 위해 res를 문자열로 변환하여 my_num에 할당하고 my_num의 큰 자리부터, nums의 첫 번째 숫자부터 비교한다.
5. 만약 my_num[i]와 nums[idx]가 같다면 서로 인덱스를 한 칸씩 이동한다.
6. idx를 통해 nums를 다 돌았다면 빠져나온다.

 

🧑🏻‍💻 Code

def solve(nums):
    res = 0 # 1
    idx = 0 # 2
    while idx < len(nums):
        res += 1 # 3
        my_num = str(res)
        for i in range(len(my_num)):
            if my_num[i] == nums[idx]: idx += 1 # 5
            if idx == len(nums): break # 6
    print(res)

if __name__ == "__main__":
    nums = input()
    solve(nums)

 

💬 소감

실버인데 어려웠다...

아무래도 너무 그리디하게만 살아서 그런가 폭 넓은 시야를 가지지 못 했던 것 같다.