[백준] 1515 수 이어 쓰기 with Python

📌 BOJ 1515 수 이어 쓰기

💡 조건

1. 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다.

2. 다솜이가 숫자의 일부를 지웠고, 지워지기 전의 숫자를 다시 쓰려고 하니 N이 기억나지 않는다.

3. 남은 수를 이어 붙인 수가 주어질 경우, N의 최솟값을 구하는 문제.

4. 일부 숫자를 지우고 남은 수를 이어붙인 수가 주어지며, 이 수는 최대 3000자리.

5. 구현, 문자열, 브루트포스 알고리즘 유형의 문제

🖥 소스 코드

from sys import stdin

data = stdin.readline().rstrip()
s, i = '', 1


def check(s):
    t = list(s)
    k = list(data)

    while 1:
        if len(t) < len(data):
            return ' '

        else:
            i = 0
            chk = 0
            while 1:
                if i >= len(k) or i >= len(t):
                    if chk:
                        return ''.join(t)
                    else:
                        return ''.join(t[:len(data)])

                if t[i] != k[i]:
                    t.pop(i)
                    chk = 1
                else:
                    i += 1

while 1:
    s += str(i)

    # check
    tf = check(s)

    if tf[:min(len(tf), len(data))] == data:
        print(i)
        break

    # tf = False
    if tf != ' ':
        s = tf
        i += 1
    else:
        i += 1

🔖 예제 및 실행결과

예제

00000000000000000000000000000000000000000000000000000000000000000000000

실행결과

400

⌨️ 문제 풀이

1. 1부터 수를 늘려가면서 완전탐색을 실행하면 된다.
   i, s 는 각각 1과 '' 로 초기화 한 뒤, while 1: 반복으로 i를 늘려주며 순회한다.

2. s 에 str(i)를 이어 붙이고 check() 함수에서 검사를 실시한다.

3. check 함수에서는 사용자에게 입력받은 data와 while 반복문을 통해서 이어 붙인 숫자의 길이를 검사한다.
   만약, 길이가 같지 않으면 ' '를 리턴해준다.
   만약, 길이가 같다면 data 배열과 이어 붙인 숫자의 각 자리를 검사하여 틀린것은 pop() 으로 빼준다
   길이가 같은 경우, 각 자리가 모두 동일했다면 chk 변수는 0이고 data의 길이만큼 반환
   길이가 다른 경우, 각 자리를 검사하고 pop()을 사용해 숫자를 뺀 이어 붙인 수를 반환

4. check 함수에서 반환받은 tf 변수는 ' ' 혹은 3번의 결과값을 가지고 있다.
   만약 tf 변수가 data의 길이와 tf의 길이 중 짧은 길이만큼 잘라냈을 때, data의 길이와 같다면
   현재의 i를 출력해주고 while을 종료한다.

5. 4번에서 종료가 안되었고 tf 가 ' '과 다르다면,

   • s는 tf로 저장해주고, i 를 1만큼 증가시켜준다.
   • 이 때 tf는 이어 붙인 수에서 숫자를 지운 상태이다.*

6. 4번에서 종료가 안되었고, tf 가 ' '과 같다면,

   • i 를 1만큼 증가시켜준다.
   • data 변수와 단 한자리도 같지 않아 이어 붙인 수가 pop()에 의해 다 뽑힌 것.*

💾 느낀점

1. 틀렸습니다와 런타임에러가 날 괴롭혔다.
   그 이유는 아래와 같다.

   • 문자열을 이어 붙이다 보면 10의 자리를 붙이게 되는데 그 순간 data 변수의 길이보다 이어 붙인 수의 길이가 길어질 때 검사하다가 오류.
   • 반환할 때도 이미 data 변수와 길이가 같거나 혹은 길이가 길게나와서 답도 제대로 안나왔다.

2. 인덱싱에 매우 약하다. 이를 극복하려면 반복 밖에는 없을 것 같다.