백준 17218번. 비밀번호 만들기 (Python / 파이썬)

문제

최근 들어 개인정보 유출에 대한 뉴스를 많이 본 수형이는 한 사이트의 비밀번호가 유출 되더라도 다른 사이트에서 똑같은 비밀번호로 접속할 수 없도록 사이트마다 비밀번호를 다르게 설정하기로 다짐했다. 많이 고민한 결과 수형이는 눈을 감고 키보드를 막 쳐서 나온 두 문자열에서 공통으로 존재하는 가장 긴 부분 문자열을 비밀번호로 하기로 하였다. 수형이가 눈을 감고 만든 두 문자열이 주어졌을 때 비밀번호를 만드는 프로그램을 만들어보자.

입력

첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는 최대 40자이다. 빈 문자열은 주어지지 않는다. 가장 긴 부분 문자열은 반드시 하나만 존재한다.

출력

첫 번째 줄에 입력으로 주어진 두 문자열로 만든 비밀번호를 출력한다.

---

문제 풀이 

두 문자열이 주어졌을 때 문자열에서 공통으로 존재하는 가장 긴 부분 문자열을 구하는 문제이다. 

가장 긴 부분 문자열을 구하기 위해 DP를 이용하였다. 

dp[X][Y]는 문자열 A에서 0~X-1 까지와 문자열 B에서 0~Y-1 까지 중 가장 긴 부분 문자열의 길이를 저장한다. 

 

만약 A의 i번째와 B의 j번째 문자가 같다면 

dp[i + 1][j + 1] = dp[i][j] + 1이다. 즉, 직전까지 구한 가장 긴 부분 문자열의 길이에서 1을 더해주는 것이다. 

만약 다른 문자라면 

dp[i + 1][j + 1]은 dp[i][j + 1]과 dp[i + 1][j] 중 큰 값을 넣어주면 된다.  

이 과정을 반복하면 dp배열을 모두 구할 수 있다. 

 

이제 dp 배열을 이용해 가장 긴 부분 문자열을 출력해주면 된다. 

만약 dp[len_a][len_b] 과 dp[len_a - 1][len_b] 값이 같다면 len_a를 하나씩 감소하고

dp[len_a][len_b] 과 dp[len_a][len_b - 1] 값이 같다면 len_b를 하나씩 감소시킨다.

이 과정을 반복하면 가장 긴 부분 문자열의 길이가 달라지는 구간까지 이동할 수 있다. 

만약 가장 긴 부분 문자열의 길이가 달라지는 구간을 만나면 

공통 문자열이 나왔다는 뜻이므로 문자열에서 해당 문자를 출력해준다. 

이 과정을 반복하면 가장 긴 부분 문자열을 출력할 수 있다. 뒤에서부터 가장 긴 부분 문자열을 구했으므로 출력할 때 뒤집어서 출력한다. 

---

My Code

a = input()
b = input()

len_a = len(a)
len_b = len(b)

dp = [[0] * (len_b + 1) for _ in range(len_a + 1)]

for i in range(len_a):
    for j in range(len_b):
        if a[i] == b[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1 
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

res = ''
while dp[len_a][len_b] != 0: 
    if dp[len_a][len_b] == dp[len_a - 1][len_b]:
        len_a -= 1 
    elif dp[len_a][len_b] == dp[len_a][len_b - 1]:
        len_b -= 1 
    else:
        res += a[len_a - 1]
        len_a -= 1 
        len_b -= 1 

print(res[::-1])