두 문자열의 공통된 부분을 찾는 문제인데, 이어져 있어야 하느냐 아니냐로 답이 달라진다. 표를 채우는 코드는 거의 같고 한 줄이 다르다.
부분 수열
떨어져 있어도 순서만 맞으면 된다.
a = 'abcda'
b = 'abc'
l_a, l_b = len(a), len(b)
matrix = [[0] * l_a for _ in range(l_b)]
for x in range(l_a):
for y in range(l_b):
if a[x] == b[y]:
matrix[y][x] = matrix[max(0, y - 1)][max(x - 1, 0)] + 1
else:
matrix[y][x] = max(matrix[max(0, y - 1)][x], matrix[y][max(x - 1, 0)])
print(matrix[l_b - 1][l_a - 1])
글자가 같으면 대각선 위에서 1을 더한다. 둘 다 한 글자씩 소비했다는 뜻이다.
다르면 위와 왼쪽 중 큰 쪽을 물려받는다. 한쪽 글자를 버리고 가는 것이고, 지금까지 쌓은 길이는 유지된다. 여기가 "떨어져 있어도 된다"를 만드는 부분이다.
답은 오른쪽 아래 칸이다. 두 문자열을 끝까지 다 본 결과가 거기 있다.
부분 문자열
이어져 있어야 한다.
for x in range(l_a):
for y in range(l_b):
if a[x] == b[y]:
matrix[y][x] = matrix[max(0, y - 1)][max(x - 1, 0)] + 1
li = []
for i in matrix:
li.extend(i)
ans = max(li)
else 가 없다. 글자가 다르면 0으로 남는다. 물려받지 않으므로 한 번 끊기면 다시 1부터 센다.
그래서 답을 읽는 위치도 달라진다. 오른쪽 아래 칸은 마지막 글자에서 끝나는 것만 알려주므로, 표 전체를 훑어 최댓값을 찾아야 한다.
else 한 줄과 답을 읽는 위치, 두 군데가 이 둘을 가른다.
시험한 문자열로는 차이가 안 보인다
abcda 와 abc 로 돌리면 둘 다 3이 나온다. 공통 부분이 abc 로 이어져 있어서 구분이 안 된다.
떨어뜨려 보면 갈린다.
| a | b | 부분 수열 | 부분 문자열 |
|---|---|---|---|
abcda |
abc |
3 | 3 |
abcdef |
acef |
4 | 2 |
acef 는 abcdef 안에 순서대로 흩어져 있으므로 부분 수열로는 4다. 이어진 것으로는 ef 가 최대라 2다.
경계를 max로 누른 것
보통은 0으로 채운 행과 열을 하나씩 더 붙여서 matrix[y-1][x-1] 이 항상 안전하게 하는데, 여기서는 표를 딱 맞게 만들고 max(0, y-1) 로 눌렀다.
이러면 첫 행과 첫 열에서 자기 자신을 참조하게 된다. y = 0 일 때 matrix[max(0, -1)][...] 은 matrix[0][...] 이라 위쪽 칸이 아니라 같은 행이다.
abcda / abc 에서는 답이 맞게 나와서 그냥 넘어갔는데, 다른 입력을 넣어보니 어긋난다. AGGTAB 와 GXTXAYB 의 부분 수열 길이는 GTAB 로 4인데 이 코드는 5를 낸다.
첫 행에서 같은 행의 값을 물려받아 더해버리는 경우가 생기기 때문이다. 0으로 채운 행과 열을 붙이면 안 생긴다.