[Swift] 백준 15483번: 최소 편집 - DP

15483번: 최소 편집

문제

• 주어진 A를 최소 횟수로 연산을 수행하여 B로 만드는 문제

연산의 3종류

1. 삽입: 한 위치에 문자 하나를 삽입
2. 삭제: 문자 하나를 삭제
3. 교체: 문자 하나를 다른 문자로 교체

제한사항

• 문자열은 알파벳 소문자로만 구성
• 문자열은 최대 1000글자

풀이

문제의 핵심은 얼마나 중복된 문자를 확인하는지가 중요하다.

물론 이 문제를 혼자서 해결 못했기에 이렇게 블로그에 정리 중이다.

 

편집 거리 알고리즘

위키의 Edit distance 내용을 보게 되면 다양한 종류에 대한 내용이 나온다.

글에서 이야기 하는 것은 2개의 문자열이 주어졌을 때, 편집의 최소 가중치를 이야기한다.

공통 알고리즘

예제

문자열 "kitten"을 "sitting"으로 변경할 때 가중치를 계산한다

위에서 나온 알고리즘으로 문자열이 비어있는 것과 비교를 할 때, 1개씩 삭제해야 하기에 아래와 같은 배열로 가중치를 표현한다.

	""	k	i	t	t	e	n
""	0	1	2	3	4	5	6
s	1
i	2
t	3
t	4
i	5
n	6
g	7

 

문자가 같다면 최소의 가중치를 적는다.

 

같지 않다면 삽입, 삭제 그리고 변경 연산을 통한 가중치를 확인한다

 

문자열 "ki"와 "si"의 "i"는 같은 문자이기 때문에 "k"와 "s"의 가중치와 동일하다

	""	k	i	t	t	e	n
""	0	1	2	3	4	5	6
s	1	1	2	3	4	5	6
i	2	2	1
t	3	3
t	4	4
i	5	5
n	6	6
g	7	7

 

위와 같은 계산을 반복하면 아래와 같은 배열이 완성된다.

배열의 마지막 값은 최소 편집된 가중치를 표현한다.

	""	k	i	t	t	e	n
""	0	1	2	3	4	5	6
s	1	1	2	3	4	5	6
i	2	2	1	2	3	4	5
t	3	3	2	1	2	3	4
t	4	4	3	2	1	2	3
i	5	5	4	3	2	2	3
n	6	6	5	4	3	3	2
g	7	7	6	5	4	4	3

 

코드

import Foundation

let p = Array(readLine()!), P = p.count, n = Array(readLine()!), N = n.count
var T = Array(repeating: Array(repeating: 0, count: N+1), count: P+1)
for i in 0...P { T[i][0] = i }
for i in 0...N { T[0][i] = i }
for i in 1...P {
    for j in 1...N {
        T[i][j] = p[i-1] == n[j-1] ? T[i-1][j-1] : min(T[i-1][j-1], T[i-1][j], T[i][j-1])+1
    }
}

print(T[P][N])