파이썬 문자열 문제 (find,in,KMP알고리즘) ,7575 바이러스(백준)

파이썬에서의 문자열 문제해결방법

1. in을 사용해서 포함여부 판단하기

2. find()를 사용해서 index까지 구하기

3. KMP알고리즘을 사용해서 index 또는 포함여부 구하기

 

 

1,2번은 최악의 경우 O(N*M)이지만 KMP알고리즘은 O(N+M)에 해결 가능하다.

리스트 형태로 저장하였다면 ''.join(list_name)으로 공백없는 문자열을 만들 수 있다.

 

 

1. in을 사용하기

문자열에 in을 사용해서 찾는 문자열이 포함되는지 판단 가능하다.

만약 포함된다면 True를 아니면 False값을 반환해준다.

 

ex) string='python'

print('pyt' in string) =>True

print('ppp' in string) ->False

 

 

2.find() 함수 사용하기

문자열간에 포함여부와 인덱스를 반환해준다.

포함되어 있다면 인덱스 번호를, 아니라면 -1을 반환해준다.

찾는 문자열 뒤에 인자를 추가해서 시작지점을 설정 가능하다.

 

ex)string='i hate corona Virus'
print(string.find('co')) =>7

print(string.find('ha')) =>2

print(string.find('Q')) =>-1

print(string.find('i',1)) =>15

 

 

3.KMP알고리즘 사용하기

KMP알고리즘을 사용하면 O(N+M)의 시간에 포함여부와 인덱스까지 구할 수 있다.

cantcoding.tistory.com/13?category=873347 에 정리해 두었다.

 

 

 

find와 KMP 두가지 방법을 사용해서 백준 7575번 바이러스 문제를 풀어보겠다.

www.acmicpc.net/problem/7575

7575번: 바이러스

1.접근

첫번째 코드를 여러개로 나눠보고 나머지 모든 코드에 대입해보는 방식으로 추려야한다고 생각했다.

2.풀이

바이러스의 길이는 K개 이상이라고 적혀있다. 이것은 어떠한 바이러스든 K개의 문자열 이상으로 이루어져있다는 뜻이므로 K개로 이루어진 문자열만 보면 된다.

예를들어 1 2 3 4 5로 이루어진 코드가 있고 k가 4라면 1,2,3,4와 2,3,4,5만 확인해보면 된다는 뜻이다.

따라서 (첫번째 코드의 길이-k+1)만큼 for문을 돌면서 나머지 데이터들과 비교해보면서 가능한 코드가 나올때까지 돌려보면서 확인해보면 된다.

바이러스는 반대방향도 있으므로 혹시 정방향으로 실패했더라도 리스트를 거꾸로부터 한번더 확인해보아야 한다.

데이터가 쉬운지 in과 find를 사용한 방법이 훨씬 빨랐다.

3.코드

4.배운점

• in과 find는 최악의 경우 O(N*M)이므로 주의하자

• 바이러스 문자열 길이가 K이상이면 최소 K로된 길이만 찾으면 되는걸 아는게 오래걸렸다.

• ''.join()을 사용해서 문자열 만드는 것을 까먹지 말자. find,in은 문자열만 가능하다