[백준 1120 ] 문자열 문제 풀이

• [백준 1120 ] 문자열 문제 풀이
  • Key Point
  • Solution

[백준 1120 ] 문자열 문제 풀이

문제링크

두 개의 문자열이 주어질 때, 최대한 문자열을 겹치게 만드는 문제로, 최소한으로 덜 겹치는 수를 찾으면 됩니다.

# input
abd abcd

# output
1

$abcd$에서 겹치는 부분은 $abc$, $bcd$ 2가지가 가능하며, 이 중에서 $abc$가 $abd$ 와 차이가 1로 가장 작습니다.

 

따라서 $abdd$ 형태가 $abcd$와 차이가 1로 가장 작게 됩니다. 

 

 

Key Point

• a의 길이는 b의 길이보다 짧다.
• a의 좌우에 아무 알파벳이나 넣을 수 있는 것은 b에서 위치를 잡으면, a의 위치를 제외한 나머지 부분은 알파벳이 동일하다고 여길 수 있습니다.

Solution

a, b = input().split()
count = len(b)

for i in range(len(b)-len(a)+1):
    summ = sum([True for x,y in zip(a,b[i:len(a)+i]) if x!=y])
    count = min(count, summ)
print(count)