[백준] 1120 문자열 (파이썬)

문제를 풀면서 느끼기에 실버4보다 어려웠다. 오른쪽 문자열에서 왼쪽 문자열이 포함되어 있는 개수를 세면 쉽게 풀거 같다는 느낌은 받았는데, 인덱스 처리를 어떻게 해야할지 감이 안잡혀서 문제 그대로 왼쪽과 오른쪽에 문자열을 추가해서 비교하는 방식으로 구현했다. 다른 사람들 풀이를 보니까 이중 for문으로 간단하게 풀어서 좀 허탈했던 문제였다.

import sys
input = sys.stdin.readline

a, b = input().rstrip().split()
diff = len(b) - len(a)
word_set = set()
ans = sys.maxsize

def check(a, b): 
  res = 0
  for i in range(len(b)):
    if a[i] == "*":
      continue
    elif a[i] != b[i]:
      res += 1
  return res

def solution(inp, remain):
  global ans, b
  if remain == 0:
    ans = min(ans, check(inp, b))
    return 0

  left = "*" + inp
  right = inp + "*"

  if left not in word_set:
    solution(left, remain-1)

  if right not in word_set:
    solution(right, remain-1)

  word_set.add(left)
  word_set.add(right)

if len(a) == len(b):
  ans = check(a,b)
else:
  solution(a, diff)

print(ans)