[백준] 5882 공통 부분 문자열 Python

문제 링크 : 5582번: 공통 부분 문자열

5582번: 공통 부분 문자열

 

풀이 코드 : GIthub

문제

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

풀이

• DP문제이다.
• 그림으로 표현하면 다음과 같다.

• ‘ABCDF’, ‘CDFEQ’ 2가지 String이 있다고 할 때
• 각 String의 한글자씩 반복하면서 돌면서 두 String에 같은 글자가 있으면 해당 인덱스에서 대각선 위 값을 참조하여 해당 값에 +1 한값을 현재 인덱스에 넣는다.
• 인덱스의 넣은값을 현재 max 값과 비교하여 max보다 크다면 교체한다.

제출 1 → 메모리 초과 오답

import sys

input1 = sys.stdin.readline().rstrip()
input2 = sys.stdin.readline().rstrip()

dp_array = [[0] * (len(input2)+1) for _ in range(len(input1)+1)]

max_value = 0

for i in range(1, len(input1)):
    for j in range(1, len(input2)):
        if input1[i] == input2[j]:
            dp_array[i][j] = dp_array[i-1][j-1] + 1
            if max_value < dp_array[i][j]:
                max_value = dp_array[i][j]

print(max_value)

• 위 풀이방법으로 코드를 구현하였으나 메모리초과 오류가 발생하였다.
• 2개의 String길이만큼 2d list가 생성되어 input이 길어지면 메모리 초과가 나는것 같다.
• 이 문제 해결 필요

제출 2 → 정답

import sys

input1 = sys.stdin.readline().rstrip()
input2 = sys.stdin.readline().rstrip()

dp_array = [[0] * (len(input2)+1) for _ in range(0, 2)]

max_value = 0

for i in range(0, len(input1)):
    dp_array[0] = dp_array[1]
    dp_array[1] = [0] * (len(input2)+1)
    for j in range(0, len(input2)):
        if input1[i] == input2[j]:
            dp_array[1][j] = dp_array[0][j-1] + 1
            if max_value < dp_array[1][j]:
                max_value = dp_array[1][j]

print(max_value)

• 2d list크기를 줄이기 위해 기존 2개의 String으로 DP를 위한 2d list를 만드는 것이 아닌 1개로 만듬
• 앞서 예시를 든 ‘ABCDF’, ‘CDFEQ’ 2가지 String예시에서
• 아래처럼 첫번째 row이전 String의 문자를 비교한 결과를 2번째 row에는 현재 String의 문자를 비교한 결과를 저장

• 다음문자를 비교할 때는 두 번째 row를 첫 번째 row로 옮겨 다시 계산

• 이를 계속 반복

• 이를 이용하면 n * m DP list를 유지할 필요 없이 2 * n DP list를 유지하면 되므로 메모리 사용량을 줄일 수 있었다.