Hanbit the Developer
[Python] 7575번: 바이러스 본문
https://www.acmicpc.net/problem/7575
7575번: 바이러스
첫 번째 줄에는 감염된 프로그램의 개수 N 과 바이러스 코드 추정을 위한 최소 길이를 나타내는 정수 K 가 주어진다. 단, 2 ≤ N ≤ 100이고, 4 ≤ K ≤ 1,000이다. 두 번째 줄부터 각 프로그램에 대한
www.acmicpc.net
import sys
input = sys.stdin.readline
def get_pi(keyword):
keyword_length = len(keyword)
pi = [0]*keyword_length
j = 0
for i in range(1, keyword_length):
while j > 0 and keyword[i] != keyword[j]:
j = pi[j-1]
if keyword[i] == keyword[j]:
j += 1
pi[i] = j
return pi
def it_there_one_keyword(string, keyword, pi):
string_length = len(string)
i, j = 0, 0
while i < string_length:
if string[i] == keyword[j]:
i += 1
j += 1
else:
if j == 0:
i += 1
else:
j = pi[j-1]
if j == K:
return True
return False
def has_virus():
for i in range(K, len(info[0])+1):
# Set target
cur_str = info[0][i-K:i]
cur_str_reversed = list(reversed(cur_str))
# Search
flag = True
pi = get_pi(cur_str)
pi_reversed = get_pi(cur_str_reversed)
for j in range(1, N):
result1 = it_there_one_keyword(info[j], cur_str, pi)
result2 = it_there_one_keyword(info[j], cur_str_reversed, pi_reversed)
if result1 == False and result2 == False:
flag = False
break
# If keyword was searched in every other strings
if flag:
return True
return False
if __name__ == '__main__':
N, K = map(int, input().split())
info = []
for _ in range(N):
_ = int(input())
info.append(list(map(int, input().split())))
if(has_virus()):
print("YES")
else:
print("NO")
has_virus()가 메인 로직입니다. 가장 바깥 for문은 첫번째 프로그램을 기준으로, K자씩 가져오기 위함입니다. 예를 들어, K = 4이고, 첫 프로그램이 abcde이면 abcd, bcde 순서로 접근합니다. cur_str, cur_str_reversed에 해당 문자열과 뒤집힌 문자열을 가져옵니다.
다음으로 검색을 시도합니다. 빠른 검색을 위해 KMP 알고리즘을 사용합니다. 다만, 이전에 설명한 적이 있으므로 설명을 생략하고, 관련 링크로 대체합니다.
[Python] 백준 1893번: 시저 암호
https://www.acmicpc.net/problem/1893 1893번: 시저 암호 암호학에서, 시저 암호(또는 시프트 암호, 시저 코드, 시저 시프트)는 가장 간단하면서 많이 알려진 암호화 기술 중 하나이다. "시저 암호"라는 이름
rccode.tistory.com
2개의 문자열에 대한 pi 테이블을 함수를 통해 가져옵니다.
다음으로 반복문을 수행합니다. 이것의 목적은, 1번째 프로그램을 제외한 모든 프로그램에 현재 문자열 2개 중에 1개라도 모두 포함하는지를 검사하는 것입니다. 즉 문제에서 설명한 것처럼, 현재 문자열이 현재 모든 프로그램에 나타나는지를 KMP를 통해 검색합니다.
이렇게 나머지 프로그램들에 대해 검색을 하였는데, 모든 프로그램에서 문자열이 검색되었을 경우 flag 값이 True를 가리키게 됩니다. 이 경우 has_virus() 함수는 True를 반환합니다.
마지막으로, 이 함수의 결과에 따라 YES, NO를 출력해주면 됩니다.
'Algorithm > 백준' 카테고리의 다른 글
[Python] 백준 1256번: 사전 (0) | 2021.08.30 |
---|---|
[Python] 백준 1562번: 계단 수 (0) | 2021.08.29 |
[Python] 백준 3356번: 라디오 전송 (0) | 2021.08.27 |
[Python] 백준 2533번: 사회망 서비스(SNS) (0) | 2021.08.26 |
[Python] 백준 2568번: 전깃줄 - 2 (0) | 2021.08.25 |