[Python] BOJ(백준) 1230 문자열 거리

https://www.acmicpc.net/problem/1230

 

틀렸던 문제 다시 풀기 3일차.

골드1을 보고 당황 했지만,,, 하루에 딱 한 시간만 투자한다는 생각으로 도전했다.

4일정도 걸린 것 같은데, 문제를 고민하는 데 2일, 인터넷에 다른 코드를 이해하는 데 2일이 걸렸다.

 

문자열 O를 N으로 만들기 위해 추가해야 하는 최소 '문자열'의 개수를 구하는 문제다.

우선, 내 머리만으로 해결하진 못 했다.

 

처음에는 단순하게 앞에서부터 비교하면서 O에 없는 문자를 카운트 했다.

연속 여부를 고려해 문자열 개수를 카운트 했다. (틀린 방법이니 자세히 설명하진 않겠다.)

 

그리고 2차원 표에 O[:i] 를 이용해 N[:j] 를 만드는 데 필요한 최소 문자열 개수를 구했다.

근데 정말 이리보고 저리봐도 규칙을 끌어낼 수 없었다.

aba / aababa 같은 경우 O[0]의 'a'를 N과 매칭할 때 몇 번째 a를 선택한 것인지 구분할 방법이 떠오르지 않았다.

(i = 0, j = 3 일 때, 'a' + 'aba' / 'a' + 'a' + 'ba' / 'aab' + 'a' 경우의 수가 생기고,

최소값이 2라고 하더라도 어떤 경우인지 나타낼 수 있는 방법을 못 찾았다.)

 

--- 본론 ---

 

그래서 이미 풀이된 코드를 참고했다.

풀이 코드들은 공통적으로 3차원 dp 배열을 이용했다. 

dp[i][j][0]과 dp[i][j][1]을 통해 문자열이 삽입 중이 아닌지, 삽입 중인지 구분했다.

사람들의 풀이마다 [0]과 [1]을 표현하는 데 있어 다른 표현을 썼지만 다 이해하기 어려웠다.

그래서 나는 삽입 중이 아니다, 삽입 중이다 로 표현하기로 했다.

 

dp[i][j][0]의 경우 이전 문자열이 삽입되지 않은 상태다. 즉, O에 포함된다는 것이다.

dp[i][j][1]의 경우 이전 문자열이 삽입된 상태다. 즉, O에 포함되지 않는다는 것이다.

 

dp[i][j][0]은 o[i] == n[j]일 때만 업데이트 된다.

o[i] == n[j]라는 것은 dp[i - 1][j - 1][0 or 1] 에서 구한 최솟값과 동일하다

예를 들어, aba / aababa 에서 i = 1, j = 2라면 'ab'로 'aab'를 만드는 최소 문자열 수를 구하는 것이다.

o[i] == n[j] 가 성립하고, 이 경우 'a'로 'aa'를 만드는 최솟값에 그대로 뒤에 'b'를 추가하면 되기에 이전 최솟값 그대로다.

여기서 dp[i][j][0] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) 이라는 점화식을 뽑아낼 수 있다.

 

dp[i][j][1]은 모든 경우에 업데이트 된다.

[1]의 의미가 삽입을 하겠다는 것이기 때문에

1) 이전에 삽입 했던 거에 이어 추가로 삽입하거나 2) 이전에 삽입하지 않았던 거에 새롭게 삽입하는 경우가 있다.

1)의 경우 dp[i][j - 1][1] 그대로 이어진다.

2)의 경우 dp[i][j - 1][0] + 1 새롭게 삽입하는 것이기에 이전 값에 1을 더한다.

여기서 dp[i][j][1] = min(dp[i][j - 1][1], dp[i][j - 1][0] + 1) 이라는 점화식을 뽑아낼 수 있다.

 

다른 언어들과는 달리, 파이썬은 배열을 만들면서 특정 값으로 초기화 할 수 있다.

따라서 dp 배열을 따로 초기화하거나, i < j 일 때 별도로 처리해 줄 필요가 없다.

 

그리고 초기값을 결정하는 것도 이해하는 데 오랜 시간이 소요됐다.

"" 빈 문자열로 aababa를 만드는 데 삽입 중이지 않는다...? dp[0][k][0]은 뭐지...? 라고 생각했는데

이전에 삽입 중이지 않으면 불가능 하기에 모두 초기값 그대로 두면 된다.

[1]의 경우는 삽입하면 되므로 모두 1이다.

""로 ""를 만드는 경우는 0이므로 이 두 부분만 별도로 초기화 해주면 된다.

 

import sys

input = sys.stdin.readline
o = input().rstrip('\n')
n = input().rstrip('\n')
os = len(o)
ns = len(n)

dp = [[[1000, 1000] for _ in range(ns + 1)] for _ in range(os + 1)]

dp[0][0][0] = 0
for i in range(1, ns + 1):
    dp[0][i][1] = 1

for i in range(os):
    for j in range(i, ns):
        if o[i] == n[j]:
            dp[i + 1][j + 1][0] = min(dp[i][j][0], dp[i][j][1])
        dp[i + 1][j + 1][1] = min(dp[i + 1][j][0] + 1, dp[i + 1][j][1])

res = min(dp[os][ns][0], dp[os][ns][1])
    
if res >= 1000: res = -1
print(res)

 

코테 자체는 경험이 많으나 파이썬 코테 경험은 없어서 애먼데서 시간을 많이 할애했다...

다른 언어 코드와 다르게 불필요한 초기화 부분을 제외하고 코드를 짰는데 계속 틀렸습니다가 나왔다.

도저히 차이점을 찾을 수가 없어서 GPT한테도 물어보고 다 했는데 입력의 문제였다.

(어쩐지 시작하자마자 틀렸대서 입출력을 의심하긴 했는데... 바보다)

 

o와 n을 입력받고 바로 출력했을 때 o뒤에는 줄바꿈이 같이 출력되었다.

C언어에서 문자열을 입력받고 또 입력 받으면 줄바꿈이 입력되는 것과 비슷한 현상이라고 생각했다.

그래서 뒷 문자열은 별도로 처리하지 않고 앞 문자열 o만 [:-1]처리를 했었다.

제대로 해결하기 위해서는 두 문자열에 모두 해줬어야 한다...

또는 본문의 코드처럼 rstrip('\n')으로 줄바꿈을 떼어내면 된다...

이거 찾는데 한참 걸렸다....................................

경험은 무시 못한다 정말...

경험 += 1