문제
두 문자열 A, B 가 주어질 때, 두 문자열 사이의 거리를 구하려 한다. 여기서 거리는 다음과 같이 정의된다. 문자열 A가 주어질 때, 여기서 하나의 연산은 하나의 알파벳을 삽입 또는 삭제하는 것을 의미한다. 문자열 A와 B 사이의 거리란, A에서 시작하여 B를 만들기 위한 최소 연산의 횟수로 정의된다. 예를 들어, 문자열 A가 “abcabcd”이고, 문자열 B가 “abccabc” 라면, 문자열 A와 B 사이의 거리는 2가 된다. 왜냐하면 문자열 A의 세 번째에 ‘c’를 삽입하고, 가장 마지막에 있는 ‘d’를 삭제하면 문자열 B를 얻기 때문이다. 두 문자열이 주어질 때, 두 문자열 사이의 거리를 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄과 두 번째 줄에 문자열이 주어지며, 이 문자열의 길이는 1000을 넘지 않는다. 주어진 문자열은 대소문자가 섞여있다.
출력
두 문자열 사이의 거리를 출력한다. (대문자 'A'와 소문자 'a'는 다른 문자로 취급한다.)
예제 입력
abcabcd
abccabc
예제 출력
2
# 접근법
a와 b인 경우를 생각해보자.
같아지는 경우는 a를 빼고 b를 넣거나 b를 빼고 a를 넣는 것이다.
어쨋든 행위 자체는 빼고, 넣다 2번을 해줘야 한다. 그래서 2이다.
이런 논리로 아래의 테이블 표를 완성하였다.
| 0 | a | b | c | a | b | c | d | |
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| a | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| b | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| c | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 |
| c | 4 | 3 | 2 | 1 | 2 | 3 | 2 | 3 |
| a | 5 | ?(4) | 3 | 2 | 1 | 2 | 3 | 4 |
| b | 6 | 5 | 4 | 3 | 2 | 1 | 2 | 3 |
| c | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 2 |
4는 (c-0)이 같아지기 위해서 행해야하는 숫자이다. 즉 a, b, c 4번을 빼면 된다는 것을 의미한다.
우리가 원하는 ? 자리에 올 값을 구한다고 생각해보자.
우선 비교문자열 a와 a가 같다. 넣고 빼는 행위가 필요가 없다는 뜻이다. 그럼 그 이전의 행위 값과 일치할 것이다.
즉 ?는 이전의 행위의 값인 4가 그대로 대입되면 되는 것이다.
if str_b[i-1] == str_a[j-1]:
arr[i][j] = arr[i-1][j-1]
그러면 이번에는 비교할 대상이 다를 경우를 생각해보자.
a와 c의 값 2가 어떻게 해서 나왔는지를 설명하면
a와 c가 다르다 즉 a와 c가 다르기 때문에 빼거나 넣는 행위를 통해 일치를 시켜줘야하는데
그 행위의 갯수는 이전 행위 + 1이 될 것이다. 여기서의 이전 행위는 위의 3과 좌측의 1이 가지고 있다. 근데 문제의 조건에서
A에서 시작하여 B를 만들기 위한 최소 연산의 횟수로 정의
라고 제한하고 있기 때문에 우리는 작은 값인 1을 택하고 현재의 행위 + 1을 해주면된다.
if str_b[i-1] != str_a[j-1]:
arr[i][j] = min(arr[i-1][j], arr[i][j-1])+1
# 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
import sys
if __name__ == "__main__":
input = sys.stdin.readline
str_a = input().strip()
str_b = input().strip()
arr = [[0]*(len(str_a)+1) for _ in range(len(str_b)+1)]
for i in range(len(arr[0])):
arr[0][i] = i
for i in range(len(arr)):
arr[i][0] = i
for i in range(1, len(arr)): # arr의 행이면서, str_b
for j in range(1, len(arr[i])): # arr의 열이면서, str_a
if str_b[i-1] == str_a[j-1]:
arr[i][j] = arr[i-1][j-1]
else:
arr[i][j] = min(arr[i-1][j], arr[i][j-1])+1
print(arr[-1][-1])
|
cs |