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

문제

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

 

 

 

풀이

234015가 입력으로 주어졌을 때 아래와 같이

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

밑줄 그어진 수가 남은 수, 그렇지 않은게 다솜이가 지워린 수인것을 알 수 있고 마지막 값인 15가 정답이다. 

 

최소인 마지막 값을 찾으려면

1부터 1씩 증가시키면서 입력으로 주어진 수( 234015 )의 앞부분부터 지워나가면 된다.

 

순차적으로 생각하면 다음과 같다.

1 -> 234015

2 -> 234015, 2 삭제

3 -> 34015, 3 삭제

4 -> 4015, 4 삭제

5 -> 015

6  -> 015

7  -> 015

8  -> 015

9  -> 015

10 -> 015, 0 삭제

11 -> 15, 1 삭제

12 -> 5

13  -> 5

14 -> 5

15 -> 5, 5 삭제

 

이때 234015 를 deque에 저장해 직접 왼쪽부터 지워나가도 되나 지워진 곳의 인덱스만 기록해서 처리 하는게 빠르다.

 

한가지 주의사항으로 아래의 예시와 같이 숫자가 커질 경우를 생각해보자

.. 생략 ...  

200 -> 221099, 2 삭제

201 -> 21099, 21 삭제

202 -> 099, 0 삭제

.. 생략 ...  

 

1씩 증가하면서 비교하고있는 200, 201, 202와 같은 수는 201 과 같이 중간에 매칭되지 않는 수가 있어도 순서만 맞으면 삭제가 가능하다는 점을 유의해야한다.

 

 

 

 

정답 코드

removed_nums = input()
search_index = 0
num = 0

while search_index < len(removed_nums):
    num += 1
    current_num = str(num)

    i = 0  # current_num의 인덱스
    while i < len(current_num) and search_index < len(removed_nums):
        if current_num[i] == removed_nums[search_index]:
            search_index += 1
        i += 1

print(num)

 

 

 

코틀린 버전의 풀이와 코드는 다음 포스팅 참조

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