백준 1120번 파이썬 풀이: 문자열

백준 1120번 문자열

 

알고리즘 분류: 문자열

 

링크: www.acmicpc.net/problem/1120

 

1120번: 문자열

 

문제

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.

두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

1. A의 앞에 아무 알파벳이나 추가한다.
2. A의 뒤에 아무 알파벳이나 추가한다.

이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

 

 

문제 파악

 

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

 

A의 앞이나 뒤에 아무 알파벳이나 추가한다고 되어있는데 주의해야할 점은

 

길이의 차가 1보다 커지면 앞과 뒤 둘다 추가될 수 있다.

 

따라서 사실상 브루트포스처럼 모든 경우를 비교해봐야한다.

 

 

코드

# 1120번

a, b = input().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]:
            count += 1
    answer.append(count)

print(min(answer))

b는 a보다 크거나 같기 때문에 처음 for문의 range를 len(b) - len(a)에서 +1을 해줘야 한다.

 

그렇지 않으면 b와 a의 길이가 같을 경우 for문이 동작하지 않는다.

 

이중 for문을 통해서 a와 b를 비교해서 같지않은경우 count를 1씩 더하고 이를 answer라는 리스트에 더해서

 

나중에 answer중 가장 작은값을 출력해주면 된다.

 

이중 for문 안에서 어떻게 동작하는지 예를 들어보자면

 

a = abcd

b = abcdef 이라고 가정했을때

 

abcd

(abcd)ef   ->   count = 0

a(bcde)f   ->   count = 4

ab(cdef)   ->   count = 4

 

answer = [0, 4, 4]

min(answer) = 0 이런식으로 동작할 것이다.