[BOJ] 문자열 (#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의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

 

 

해설 코드 

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))

분석 > 위 문제는 a의 문자를 뒤로 하나씩 밀어가면서 b와의 오차를 계산하는 방식이다. 뒤로 하나씩 문자를 미는 것은 b의 길이에서 a의 길이를 빼고 1을 더한 만큼 반복하는데, 1을 더하는 이유는 a 와 b의 길이가 같을 경우 1을 더하지 않으면 0 이 되어 반복을 실행할 수 없기 때문이다. 그리고 a와 b의 문자를 비교하는 것은 a의 길이만큼만 반복하면 되는데, 이는 a는 언제나 b보다 길이가 같거나 짧기 때문이다. 

 

예시 

 

처음 해설 코드를 보았을 때, 이해가 잘 가지 않아서 직접 예시를 만들어 어떤식으로 코드가 진행되는 지 파악해 보았다. 이렇게 i와 j의 값이 변하면서 어떻게 반복문이 진행되는지 파악해보니, 한 눈에 보니 코드가 이해가 되기 시작했다. 

 

a = abc

b = abcdef

 

a[0] = b[0]	i = 0, j = 0
a[1] = b[1]	i = 0, j = 1
a[2] = b[2]	i =0, j = 2
a[3] = b [3]	i = 0, j = 3
array = [0]
a[0] != b[1]	i = 1, j=0
a[1] != b[2]	i = 1, j = 1
a[2] != b[3]	i = 1, j = 2
a[3] != b[4]	i = 1, j = 3
array = [0,4]
a[0] != b[2]	i = 2, j = 0
a[0] != b[3]	i = 2, j = 1
a[0] != b[4]	i = 2, j = 2
a[0] != b[5]	i = 3, j = 3
array = [0,4,4]