[Goldman Sachs 인터뷰] 편집 거리

풀이

 두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다.

 

1. 삽입: 특정한 위치에 하나의 문자를 삽입합니다.

2. 삭제: 특정한 위치에 있는 하나의 문자를 삭제합니다.

3. 교체: 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다.

 

 이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미합니다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요. 예를 들어 "sunday"와 "saturday"의 최소 편집 거리는 3입니다.

 

입력 조건

- 두 문자열 A와 B가 한 줄에 하나씩 주어집니다.

- 각 문자열은 영문 알파벳으로만 구성되어 있으며, 각 문자열의 길이는 1보다 크거나 같고, 5,000보다 작거나 같습니다.

 

출력 조건

- 최소 편집 거리를 출력합니다.

 

입력 예시1

cat
cut

 

출력 예시1

1

 

입력 예시2

sunday
saturday

 

출력 예시2

3

---

 

 아이디어를 떠올리기 쉽지 않은 문제입니다. 처음에는 단순히 두 단어의 차이만큼 글자를 더한 뒤, 비교하는 방식으로 풀어봤습니다.

str1 = input()
str2 = input()

left = list(str1) if len(str1) >= len(str2) else list(str2)
right = list(str2) if len(str1) >= len(str2) else list(str1)
diff = len(left) - len(right)

cnt = 0
for i in range(len(left)):
    if diff > 0:
        if left[i] != right[i]:
            cnt += 1
            right.insert(i, left[i])
            diff -= 1
    else:
        if left[i] != right[i]:
            cnt += 1
            
print(cnt)

 테스트 케이스에 대해서는 위와 같은 방법으로도 정답을 받을 수 있습니다. 다만 위 코드는 '단어의 길이'에 우선순위를 두고 있습니다. 따라서 두 단어의 길이가 차이가 나는만큼 우선 더해주고, 다른 연산을 후에 해줍니다. 그러나 실제로는 삽입 연산이 언제나 다른 연산보다 우위에 있는(greedy한) 경우라고 보장할 수는 없습니다.

---

코드

 따라서 모든 케이스에 대해서 고려할 수 있도록 2차원 리스트를 초기화여 DP 문제로 푸는 것이 바람직합니다.

input1 = input()
input2 = input()

n = len(input1)
m = len(input2)

str1 = [0] + list(input1)
str2 = [0] + list(input2)

table = [[0] * (m + 1) for _ in range(n + 1)]

for i, j in enumerate(range(n + 1)):
    table[j][0] = i
for i, j in enumerate(range(m + 1)):
    table[0][j] = i
    
for r in range(1, n + 1):
    for c in range(1, m + 1):
        if str1[r] == str2[c]:
            table[r][c] = table[r - 1][c - 1]
        else:
            table[r][c] = min(table[r][c - 1], table[r - 1][c], table[r - 1][c - 1]) + 1
    
print(table[n][m])

---

풀이

 두 단어를 입력받아 리스트로 만든 뒤, 맨 앞에 임의의 원소(여기서는 0)를 패딩해줍니다. 이는 이후에 테이블의 인덱스와 헷갈리지 않게 하기 위함입니다. 마찬가지로 DP 테이블을 초기화해주되, 길이가 0인 문자열에 대해서도 고려하도록 각 행과 열을 하나씩 더 만들어줍니다.

input1 = input()
input2 = input()

n = len(input1)
m = len(input2)

str1 = [0] + list(input1)
str2 = [0] + list(input2)

table = [[0] * (m + 1) for _ in range(n + 1)]

 이때 그래프가 의미하는 것은 '첫 번째 단어의 i번째 인덱스까지를 두 번째 단어의 j번째 인덱스까지로 바꿀 때 필요한 연산의 최소 횟수'입니다. 예를 들어 단어가 'sunday', 'saturday'일 때 table[2][3]은 'su'를 'sat'로 바꿀 때 필요한 연산의 최소 횟수를 의미합니다.

 

 0번째 행과 0번째 열은 각각 빈문자열의 변환을 의미하므로 언제나 추가하는 연산밖에 하지 못합니다. 따라서 수를 1씩 증가시켜가며 초기화해줍니다.

for i, j in enumerate(range(n + 1)):
    table[j][0] = i
for i, j in enumerate(range(m + 1)):
    table[0][j] = i

 여기까지 오면 테이블은 다음과 같은 형태가 됩니다.

[[0, 1, 2, 3, 4, 5, 6, 7, 8],
 [1, 0, 0, 0, 0, 0, 0, 0, 0],
 [2, 0, 0, 0, 0, 0, 0, 0, 0],
 [3, 0, 0, 0, 0, 0, 0, 0, 0],
 [4, 0, 0, 0, 0, 0, 0, 0, 0],
 [5, 0, 0, 0, 0, 0, 0, 0, 0],
 [6, 0, 0, 0, 0, 0, 0, 0, 0]]

 이제 본격적으로 점화식을 작성합니다. 점화식은 다음과 같습니다.

if 첫번째단어[i] == 두번째단어[j]:
	table[i][j] = table[i - 1][j - 1]
else:
	table[i][j] = min(table[i][j - 1](삽입), table[i - 1][j](삭제), table[i - 1][j - 1](교체)) + 1

 이것을 코드로 구현하여 테이블의 n번째 행의 m번째 열까지 업데이트시킵니다.

for r in range(1, n + 1):
    for c in range(1, m + 1):
        if str1[r] == str2[c]:
            table[r][c] = table[r - 1][c - 1]
        else:
            table[r][c] = min(table[r][c - 1], table[r - 1][c], table[r - 1][c - 1]) + 1

 이때 n, m 인덱스의 값이 바로 정답이 됩니다.