[Python] 백준/BOJ 1515번: 수 이어 쓰기 (Silver 3)

💻 Problem

문제 보러 가기

 

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

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

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

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

 

💡 Approach

1부터 숫자를 하나씩 늘리면서 입력값과 비교한다.

그 숫자 역할이 n이고 입력값은 num이다.

n을 하나씩 늘리면서 num의 한 글자씩 비교한다.

n에 들어가는 숫자에 num[i]가 있으면 i를 증가시킨다.

 

num = '231112'인 예시는 아래와 같다.

n	num[i]	i
1	2	0
2	2	0 → 1
3	3	1 → 2
4	1	2
5	1	2
6	1	2
7	1	2
8	1	2
9	1	2
10	1	2 → 3
11	1	3 → 4 → 5
12	2	5 → 6

11의 경우 n[0] == num[3]과 같고, n[1] == num[4]와 같다.

그래서 n이 11일 때는 i가 두 번 증가한다.

 

✏️ Solution

import sys
from collections import deque
input = sys.stdin.readline

num = input().rstrip()

n, i = 1, 0
while True:
    queue = deque(list(str(n)))

    while queue and i < len(num):
        x = queue.popleft()

        if num[i] == x:
            i += 1
    
    if i == len(num):
        break

    n += 1

print(n)

11 같은 두 자리수 이상의 숫자를 처리하기 위해 큐로 한 자리씩 검사하는 코드이다.

 

import sys
input = sys.stdin.readline

num = input().rstrip()
n, i = 1, 0
while True:
    for s in str(n):
        if num[i] == s:
            i += 1
            if i == len(num):
                print(n)
                exit()
    n += 1

큐를 쓰지 않고 반복문으로 풀어도 가능하다.