[알고리즘][파이썬]1120-문자열

문제

코드

1.

import sys
A,B = sys.stdin.readline().strip().split()


min = len(B)
for i in range(len(B)-len(A)+1):
    count =0
    for j in range(len(A)):
        if(A[j]!=B[i+j] and i+j < len(B)):
            count+=1
    if(min>count):
        min =count
   
print(min)

2.

import sys
A,B = sys.stdin.readline().strip().split()

answer =[]
for i in range(len(B)-len(A)+1):
    count =0
    for j in range(len(A)):
        if(A[j]!=B[i+j] and i+j < len(B)):
            count+=1
    answer.append(count)
   
print(min(answer))

1번이 원래 내가 쓴 코드이다. 2번 코드처럼 리스트에 append 하고 min을 사용하는 방법도 유용한 거 같다!

 

문제 풀이

이 문제는 주어지는 A와 B를 비교해서 길이를 맞춘 다음에 몇 개가 다른지를 알아내는 문제이다.

앞뒤에 어떤 알파벳이 추가 되냐보다

추가된 후 원래 있던 알파벳이 해당 인덱스에서 얼마나 일치하는가가 중요한 문제이다.

 

for문을 이용해 A단어를 한칸씩 밀면서 해당 인덱스의 B 단어와의 차이를 구하고 

그 차이가 가장 작을 때가 정답이라고 할 수 있다!

 

예시

a = abcd

b = abcdef

 

abcd

(abcd)ef   ->   count = 0

a(bcde)f   ->   count = 4

ab(cdef)   ->   count = 4

답은 0이다!

 

✍️브루트 포스 알고리즘
-brute: 무식한, force: 힘   무식한 힘
-완전탐색 알고리즘
-가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다