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

링크🔗

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

---

🗒️파이썬 코드 풀이

lst = list(input())

cnt = 0
while lst:
    cnt += 1 
    str_cnt = str(cnt)

    while str_cnt and lst:
        if lst[0] == str_cnt[0]:
            lst = lst[1:]
        str_cnt = str_cnt[1:]
        
print(cnt)

 

1. 브루드 포스 방식으로 문제 풀이를 진행한다. 

(cnt 값을 계속 증가시켜, lst에 있는 숫자와 비교)

 

2. while을 통해 완전히 lst가 비워질 때 까지, 계속 cnt 값을 증가시킨다. 

 

3. lst와 비교를 위해 cnt를 문자열로 바꿔준다.

 

4. while str_cnt and lst  구문에서 lst도 반드시 포함시켜야한다.  그렇지 않으면 IndexError 발생

거의 대부분 str_cnt 쪽에서 값이 비워져 두번째 while문을 탈출하지만, 
두번째 while 진행 중, lst가 비워져 있어서 lst[0]을 실행 못하는 경우가 있다. 

 

5. str_cnt의 왼쪽부터 하나 하나 없애면서 lst 왼쪽부터 비교를 한다. 

그리고 같은 값이 되면 lst[0]을 없애주고, 다시 비교를 한다.  (str_cnt와 lst 둘 중 하나가 있을 때 까지 )

ex)  cnt = '11' ,  lst=[1,1,1] 이라고 가정

두번째 while문에서,
if 조건 만족 하므로 cnt = '1', lst=[1,1]로 변경

아직 두번째 while문 조건과 if 문 조건 만족하므로,
cnt = '' , lst=[1] 로 변경

이제 cnt의 값이 비워졌으므로,두번째 while 문 탈출 후
cnt = 12 , lst = [1]

 

6. lst가 빈 배열이 되면 반복문을 빠져나오게 되고, 그때의 cnt가 답이 된다.

 

 

📕 내 풀이 (카운트 초과)

lst = list(input())

cnt = 0
while lst:
    cnt += 1 
    print(cnt,lst)
    if lst[0] in str(cnt):
        lst = lst[1:]
    
print(cnt)

 

1. 위에 정답 코드의 두번째 while문을 쓰지 않고, if ~ in을 통해서 비교를 했다.

 

2. 이거 같은 경우, 이런 예제의 정답을 잘 출력하지 못한다.

1111111

 

 

앞서 했던 예시와 같이,

cnt = 11이면, lst의 1을 두번 빼야하는데, 내 코드 같은 경우 한번만 제외하기 때문이다.

 

📌  문제 코멘트

코드만 보면 짧아서 쉬워보이지만, 구현하는데 어려웠다

특히, 여러 변수와 조건들을 생각을 잘 못했는데, 이러한 문제 유형을 기억해야겠다.

 

맨 처음 풀이는 브루드 포스 방식이 아니라,

현재 위치의 수가 다음 위치의 수보다 클 때  또는 같을 때로 cnt를 구했는데,

이거 같은 경우도 너무 생각해야 할 변수가 많아서 도중에 포기했다.

 

---

📚문제

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

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

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

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

입력

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

출력

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

예제 입력 1 복사

1234

예제 출력 1 복사

4

예제 입력 2 복사

234092

예제 출력 2 복사

20

예제 입력 3 복사

999909

예제 출력 3 복사

49

예제 입력 4 복사

82340329923

예제 출력 4 복사

43

예제 입력 5 복사

32098221

예제 출력 5 복사

61

예제 입력 6 복사

1111111

예제 출력 6 복사

14

예제 입력 7 복사

00000000000000000000000000000000000000000000000000000000000000000000000

예제 출력 7 복사

400

예제 입력 8 복사

345029834023049820394802334909240982039842039483294792934790209

예제 출력 8 복사

279