난이도

Gold 5

문제

상근이는 DNA의 일부를 교체해 복제를 시작하는 바이러스를 발견했다.

이 바이러스는 어떤 DNA의 연속된 일부분을 다른 DNA로 교체한다.

이제, 다음 연구를 위해 바이러스에 의해 교체된 DNA의 길이를 구해보려고 한다.

바이러스에 감염되기 전 DNA와 감염된 후 DNA가 주어진다. 두 번째 DNA로 바뀌기 위해 첫 번째 DNA에 삽입되어야 하는 연속된 DNA 조각의 길이를 구하는 프로그램을 작성하시오.

연속된 DNA 조각은 삽입되기 전, 원래 그 자리에 있는 DNA를 제거할 수도 있다.

입력

첫째 줄에 바이러스에 감염되기 전 DNA, 둘째 줄에 감염된 후의 DNA가 주어진다.

DNA는 {A, G, C, T}로만 이루어져 있으며, 길이는 1보다 크거나 같고, 105보다 작거나 같다.

출력

첫째 줄에 바이러스에 의해 삽입된 DNA 길이의 최솟값을 출력한다.

예제 입력

AAAAA
AGCGAA

예제 출력

3

해설 및 후기

투-포인터와 유사한 방법으로 해당 문제를 풀이했다. 원래 DNA에서 삭제는 얼마나 해도 상관없다는 점에서 착안하여, 앞쪽에서부터 다른 DNA가 나올 때까지 증가시키고, 뒤쪽에서부터 다른 DNA가 나올 때까지 증가시켰다. 이후 n-lst > fst인 경우 n-fst-lst를 출력하고, 그렇지 않은 경우 예외를 처리하기 위해 삭제만 된 경우, 삽입만 된 경우를 분기하여 처리하였다.

제출 코드

a = list(input())
b = list(input())
rA = list(reversed(a))
rB = list(reversed(b))
n = len(b)
m = len(a)
fst = -1
lst = -1

i = 0
while(i < n):
    if(i >= m):
        break

    if(a[i] != b[i]):
        break
    i+=1
fst = i

i = 0
while(i<n):
    if(i >= m):
        break

    if(rA[i] != rB[i]):
        break
    i+=1
lst = i

#print(f"fst:{fst}, lst:{lst}")

if(n-lst > fst):
    print(n-fst-lst)
else:
    if(n < m):
        print(0)
    else:
        print(n-m)