[Python] 1515. 수 이어 쓰기

문제

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

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

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

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

---

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

 

풀이

처음엔 문제를 약간 잘못 이해했는데, 지워진 숫자들이 온전한 숫자들이라고 생각했다. (예를 들어 ... 10 11 12 ... 면 11만 지우지 01 이나 2를 지우지는 않는다고 생각했다.) 그래서 내가 이해한 것을 바탕으로 제대로 동작하는 코드를 작성해 보았다. 그리디 알고리즘과 같이 최솟값을 1부터 시작해서 갱신했고, 현재 최솟값의 자릿수 값을 따로 저장해서 현재 자릿수만큼 한번에 가져와 비교하는 로직을 구현하였다.

첫 번째 코드

num = input()
ans = 0  # 현재 최솟값
cnt = 1  # 몇자리수?
i = 0
while i < len(num):
    n = int(num[i : i + cnt])  # 현재 자릿수만큼 가져오기
    if ans < n:
        ans = n
    elif ans == n:
        ans += cnt * 10
    else:
        ans = cnt * 10 + n
    cnt = len(str(ans))
    i += cnt
print(ans)

그러나 다시 문제를 제대로 이해하게 되고, input 문자열에서 숫자를 무조건 하나씩만 가져온 뒤 비교해야 하는 것을 깨달았다.

전체적인 로직은 아까와 마찬가지로 최솟값을 저장&갱신하고, input에서 하나의 숫자를 가져온 뒤 그 숫자가 현재 최솟값에 존재하는 숫자인지 검사하고 존재한다면 다음 인덱스 값을 검사, 존재하지 않는다면 최솟값을 1씩 증가시킨다. 숫자가 최솟값에 존재하는지 검사하는 로직에는 for문을, input 문자열을 순회하는 전체 로직에는 while문을 사용하였다.

 

1. ans += 1로 최솟값 증가

: 아직 검사할 num이 남았다면 ans을 1씩 증가시키며 다음 num의 값에 대한 검사를 이어간다.

 

2. for a in str(ans) 로 현재 ans의 모든 자릿수에 대하여 검사

: 예를 들어 ans="1234" 이라면 이를 문자열로 바꾼 뒤 for문에 넣어 1, 2, 3, 4 각각의 숫자들이 들어오는지 전부 검사한다. num[i]=2라면 i+=1 한 뒤 ans의 3 값이 들어오는지 비교한다.

3. i < len(num) 조건 검사로 인덱스 에러 방지

: 제일 바깥 while문에서 i < len(num) 을 검사하고 있지만 내부 for문에서 i+=1을 하다 인덱스 범위를 벗어날 수 있다.

그렇기 때문에 내부 if문에서도 i < len(num) 조건 중복 검사를 해 주고 아직 검사 가능한 인덱스 값이 있을 때만 i+=1 한다.

 

최종 코드

num = input()
ans = 0
i = 0
while i < len(num):
    ans += 1
    for a in str(ans):
        if i < len(num) and a == num[i]:
            i += 1
print(ans)

 

군더더기 없이 깔끔하게 잘 구현되었다.

예시입출력을 꼼꼼히 확인하고 문제를 정확히 파악하자.