[백준/1515] 수 이어 쓰기 (Python)

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

1515번: 수 이어 쓰기

 

Difficulty : Silver 3

 

Status : Solved

 

Time : 00:30:26

 

---

 

문제 설명

 

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

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

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

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

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

1234

 

 

출력 예시

 

4

 

 

---

 

풀이

 

이 문제를 풀며 명치를 세게 얻어맏은듯한 느낌을 받았다... 이게 이렇게 어렵게 생각할 문제였던가...?

 

우선, 브루트포스로 문제를 풀되 다음과 같이 생각해보도록 하자. 지우고 남은 숫자 리스트의 현재 인덱스를 pnt라 하고, 현재 인덱스 이전까지의 모든 숫자를 사용하였을 때 가능한 최솟값을 cnt이라고 두자.

• cnt+1부터, 현재 포인터가 가리키는 숫자 하나가 포함된 최솟값을 찾는다.
  • 이를테면, 현재 pnt가 가리키는 숫자가 '3', 그리고 cnt = 27이라면, 다음에 올 최솟값은 30이 된다.
• 이 때, 다음 포인터를 확인하며 최대한 매칭되는 포인터를 검색한다.
  • 이 때 매칭은 cnt 내에 pnt가 가리키는 숫자 하나 이상이 모두 순서대로 포함되는 상황을 의미한다. 
  • 예를 들면, 현재 pnt가 가리키는 숫자가 '1', 이후에 나타나는 숫자가 '990', 그리고 cnt = 19008라고 가정하자.
  • 조건을 만족하는 다음 cnt는 19009이다.
  • 그리고 매칭을 최대한 만족하는 숫자는 '199'이 된다. ('19009')
• 매칭되는 포인터 개수만큼 포인터 pnt를 이동시키고, 앞선 조건을 만족하는 최솟값 cnt를 업데이트한다.
• 이를 포인터가 전체 숫자 리스트를 벗어날 때까지 반복하면 끝.

 

프로그래밍 지식보다는, 추상적인 문제 해결 전략을 어떻게 떠올릴지, 또 이 전략을 어떻게 구체화할지를 확인하는 문제같다. 난이도는 돌이켜보면 어렵진 않았으나, 매우 좋은 문제라고 생각된다!

 

 

풀이 코드

num_list = input().strip()
pnt = 0
cnt = 1

def isin(num, cnt) :
  if not num :
    return True
  if not cnt :
    return False
  if num[0] == cnt[0] :
    return isin(num[1:], cnt[1:])
  return isin(num, cnt[1:])

while pnt < len(num_list) :
  num = num_list[pnt]
  while True :
    if num in str(cnt) :
      break
    cnt += 1
  tmp = 1

  while pnt + tmp < len(num_list) :
    num += num_list[pnt+tmp]
    if not isin(num, str(cnt)) or len(num) > len(str(cnt)):
      break
    tmp += 1
  pnt += tmp
  cnt += 1
print(cnt-1)

풀이 완료~