BOJ 9251 : LCS (Python)

문제

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

9251번: LCS

 

 

 

코드

st1 = list(input())
st2 = list(input())

if len(st1)<len(st2):
    array1 = st1
    array2 = st2
else:
    array1 = st2
    array2 = st1

order = [0] * len(array1)
dp = [1] * len(array1)
result = 0

for i in range(len(array2)):
    if array1.count(array2[i]) == 0:
        array2[i] = 0

while array2.count(0)!=len(array2):
    for i in range(len(array1)):
        if array1[i] in array2:
            order[i] = (array2.index(array1[i]))+1
            array2[array2.index(array1[i])] = 0
    for i in range(len(array1)):
        if order[i] != 0:
            for j in range(0,i):
                if order[j]!=0 and order[j] < order[i]:
                    dp[i] = max(dp[i] , dp[j]+1)
    if result < max(dp):
        result = max(dp)
    dp = [1] * len(array1)

print(result)

 

 

 

풀이

 

문자열 리스트의 인덱스 값을 이용해 LIS로 해결할 것이다.

 

array1 에 더 긴 문자열 리스트를, array2에 더 짧은 문자열 리스트를 담는다.

array1에 array2의 알파벳이 하나도 없는 경우에는 그 알파벳 자리에  숫자 0을 대신 넣어둔다.

→ 애초에 존재하지 않는 알파벳이라는 걸 확인하기 위해

 

array1의 알파벳(array1의 i번째  인덱스에 있는 문자)이 array2에 존재하면 order[i] 에 array2에서 그 알파벳이 존재하는 (인덱스+1) 값을 대입한다.

그리고 array2에서 그 알파벳이 위치하던 자리에는 0을 대입해서 이미 체크한 곳임을 표시한다.

→ 뒤에 array1에서 또 같은 알파벳이 나왔을 때 array2에서 이미 체크한 곳은 넘기고 확인할 수 있도록 하기 위해서

 

array1의 알파벳을 다 확인했을 때마다 LIS 를 이용해 답(변수 result)을 구한다. 새로 구한 result값이 이전의 result값보다 큰 경우에는 result의 값을 새로 구한 값으로 업데이트한다. 

 

array2의 알파벳을 모두 확인했을 때 while문을 종료한다. (array2에 있는 0의 개수가 array2의 길이와 같아질 때)

 

예시)

첫번째 줄 : order 리스트 값

두번째 줄 : array1 ACAYKP

세번째 줄 : array2 CAPCAK

 

1. 처음에는 이렇게 구성이 돼있다.

0	0	0	0	0	0
A	C	A	Y	K	P
C	A	P	C	A	K

2. array1의 0번 인덱스부터 시작해서 그 알파벳이 array2에 존재하는지 확인한다.

지금은 array2의 2번째 위치에 A가  있으므로 order[0]에 2라고 저장해두고 array2의 2번째 위치의 알파벳은 0으로 바꿔준다. 

2	0	0	0	0	0
A	C	A	Y	K	P
C	0	P	C	A	K

3. 같은 방법으로 계속 진행한다.

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

4. array1을 한바퀴 다 돌면 아래와 같이 된다.

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

order 리스트를 이용해 LIS를 구하면 현재 result 는 [2,5,6] 으로 3이 된다.

아직 array2 전체가 0이 아니므로 한번 더 for문을 돌리면

 

5. 아래와 같이 된다.

2	4	5	0	6	3
A	C	A	Y	K	P
0	0	0	0	0	0

여기에서 order 리스트를 이용해 LIS를 구하면 현재 result는 [2,4,5,6]으로 4가 된다.

 

array2의 값이 모두 0이 되었으므로(array2의 알파벳을 모두 체크함.) while문은 종료된다.

답은 4다!

 

오류...

BNBNBN 과 NB 를 입력했을 때는 답이 2가 나와야하는데 1이 나온다. 이미 체크한 알파벳은 다시 볼 수 없어서 발생한 오류인 것 같은데 해결 방법을 도저히 모르겠다..