[BOJ] 9251번: LCS

https://www.acmicpc.net/

 

문제풀이

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

9251번: LCS

두 개의 문자열이 주어질 때 두 문자열에서 매치되는 가장 긴 문자열의 길이를 구하는 문제이다. 사실 어떻게 하면 풀 수 있을지 고민을 좀 했다. 생각보다 쉽게 방식이 안 떠올라서 이전에 계산한 값을 어떻게 하면 현재 계산에 적용할 수 있을지 방법을 알기위해 노력했다. 

이 문제에서는 알파벳 하나가 어떤 알파벳과 매치될지 알 수 없다는 점이 가장 어려운 점이었다. 동일한 알파벳이 반복적으로 나온다면 그 중 어떤 알파벳과 매치될지 알고 이전 값을 활용한다는게 와닿지 않았던 것 같다. 그래서 생각하다보니 문자열 두개가 있을 때 하나의 문자열에서 한개의 알파벳을 기준으로 다른 문자열에서 모든 알파벳을 찾아봐야했다. 이후 일치하는 알파벳이 나온다면 이전의 이미 검사해서 저장해뒀던 개수 값에서 최대값을 이용해서 계산할 수 있었다. 

 

예를 들어보자!

다음의 문자열이 입력으로 주어졌다고 생각한다.

ACAYKP
CAPCAK

 

첫번째 줄의 문자열을 차례로 기준으로 보고 두번째 줄의 문자열과 모두 비교한다.

 

	C	A	P	C	A	K
A	0	1	0	0	1	0

	C	A	P	C	A	K
C	1	1	0	2	1	0

	C	A	P	C	A	K
A	1	2	0	2	3	0

	C	A	P	C	A	K
Y	1	2	0	2	3	0

	C	A	P	C	A	K
K	1	2	0	2	3	4

	C	A	P	C	A	K
P	1	2	3	2	3	4

다음과 같이 배열이 변화하게된다. 같은 알파벳이 나온다면 지나온 배열에서 제일 큰 값, 개수를 가져다가 1을 더한 값을 개수로 저장한다. 

 

Python3

import sys
str1 = list(map(str, sys.stdin.readline().rstrip()))
str2 = list(map(str, sys.stdin.readline().rstrip()))
dp = [0]*len(str2)
for i in range(len(str1)):
    cnt = 0
    for j in range(len(str2)):
        if cnt < dp[j]:
            cnt = dp[j]
        elif str1[i] == str2[j]:
            dp[j] = cnt + 1
print(max(dp))

2차원 배열로도 dp배열을 구현할 수 있지만 메모리 절약을 위해 1차원 배열을 사용하여 구현했다.

여기서 중요한 점은 cnt에 큰 값을 저장해둔다는 것이다. dp배열을 돌면서 최대 개수를 저장한다. 만약 두 알파벳이 같다면 배열의 dp값은 cnt보다 작거나 같을 것이다. 그럼 두번째 조건문을 통해 구했던 최대 개수에 본인 것 카운트 1을 더해 저장한다. 마지막엔 최대 값을 출력!