https://www.acmicpc.net/problem/9252
시간 1초, 메모리 256MB
input :
- 첫째 줄과 둘째 줄에 두 문자열이 주어진다.
- 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자
output :
- 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이
- 둘째 줄에 LCS를 출력
조건 :
- 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
과거에 풀었던 문제인 BOJ 9251 LCS 문제에 그 LCS를 출력하는 조건이 하나 더 추가되었다.
우선적으로 LCS를 찾는 방법부터 다시 한번 생각해보자.
나 같은 경우 second(두 번째 문자열)를 고정 시켜 두고, first(첫 번째 문자열)의 각 알파벳을 하나씩 비교하며 LCS가 될 수 있는지를 판별하도록 하였다.
현재 확인을 하려는 first의 알파벳이 'K'라면 이 경우를 어떻게 봐야 할까.
first를 'ACAY'까지 비교해둔 값이 data배열에서 인덱스 - 1 에 저장 되어 있을 것이다.
second내의 알파벳과 비교하다가 'K'랑 동일한 값이 존재하는 인덱스에서 우리가 해야 하는 행동은'ACAY'와 'CAPCA'까지 비교해뒀던 값에 K가 동일 하니까 1을 더하는 것이다.
그렇기에 구할 수 있는 식은 이러하다.
data[i][j] = data[i - 1][j -1] + 1
겹치지 않는 알파벳이라면 현재까지 구해놓은 값중 큰 값을 가지고 와서 계속 누적한 값을 가질 수 있도록 하여야 한다.
data[i][j] = max(data[i][j -1], data[i - 1][j])
그러면 인제 지금의 문제를 다시 보도록 하자.
LCS를 저장.
LCS 자체를 저장해야한다.
그렇다면 그냥 스트링 배열을 가지도록 해서 각 문자열을 저장하게 하자.
어차피 가장 긴 문자열은 배열의 오른쪽, 아래 꼭짓점에 존재한다.
마지막에 이 값을 출력하도록 하자.
위에서 찾은 두 식의 경우에도 1을 더하는 것이 아닌 알파벳을 더하도록 하고,
max를 이용한 식은 조건문을 통해 무엇이 길이가 더 긴지 찾도록 하자.
import sys
first = [0] + list(sys.stdin.readline().rstrip())
second = [0] + list(sys.stdin.readline().rstrip())
data = [[""] * len(second) for i in range(len(first))]
for i in range(1, len(first)):
for j in range(1, len(second)):
if first[i] == second[j]:
data[i][j] = data[i - 1][j - 1] + first[i]
continue
if len(data[i][j - 1]) > len(data[i - 1][j]):
data[i][j] = data[i][j - 1]
else:
data[i][j] = data[i - 1][j]
print(len(data[len(first) - 1][len(second) - 1]))
print(data[len(first) - 1][len(second) - 1])두 문자열의 길이를 이용해 배열을 만들어야 하고, -1의 위치를 찾아야 하기에 ""빈 문자열을 추가해 준다. 문자열의 길이는 동일하지 않을 수 있다는 것을 유의 하자.
