한 달 전쯤? KMP 한창 공부할 때, 재밌게 풀었던 문제.
풀이 적으려고 북마크를 해놓았다가 이제야 풀이를 끄적여본다.

BOJ 7575 - 바이러스 링크
(2022.08.30 기준 P5)
(치팅하지 말아 마라 마라탕 먹고싶다)

문제

양의 정수들로 표현되는 여러 수열들에서 공통으로 나타나는 길이가 K 이상인 수열이 있는지 찾기

알고리즘

문자열로 생각했을 때, 여러 문자열이 있으면 공통으로 나타나는 부분 문자열을 찾는다고 생각하면 이해가 바로 갈 것이다. 그게 바로 KMP
KMP는 작동 원리를 생각하면 문자열이나 리스트나 상관없이 잘 돌아간다.

풀이

여러 프로그램이 있을 때, 모든 프로그램에서 공통적으로 나타나는 코드가 있는지 찾으면 되므로
프로그램 아무거나 하나 기준으로 잡고 그 프로그램 안에서 길이가 K인 연속 부분 수열들을 하나하나 KMP 돌리면 된다.
K 이상인 코드를 바이러스로 생각한다 했으므로 길이가 K인 코드를 찾으면 된다. (길이가 K 이상이니깐 길이가 K인 코드를 포함하기 때문)

시간초과가 나지 않을까 걱정되겠지만, 프로그램 수와 길이를 보면 크지도 않고, 중간중간에 최적화만 잘해주면 너무나도 넉넉하게 통과가 된다.

프로그램 코드를 나타내는 양의 정수 범위는 10000 이하이다.
그러므로 먼저 수가 몇번 나왔는지 체크해주는 배열을 하나 만들어 준 다음에
프로그램을 입력받고 그 프로그램 안에 수를 체크해주자.

ct = [0] * 10001
programs = []
for _ in range(N):
    input()
    program = list(map(int, input().split()))
    programs.append(program)
    for p in program:
        ct[p] += 1

코드는 모든 프로그램에서 공통적으로 나타나야 하기 때문에, 만약 어떤 수가 프로그램 수보다 적게 카운트됐다면 그 수는 바이러스가 될 수 없으므로 그 수를 포함하는 연속 부분 수열들은 전부 탈락이 된다.

이제 프로그램을 전부 입력받았으면 프로그램 하나를 기준으로 잡자.
첫번째 프로그램을 추천한다. 그냥 보기 편하기 때문? 뭐.. 아무거나 기준으로 잡고
기준 프로그램의 첫번째 코드부터 길이가 K가 되는 연속 부분 수열을 차례대로 비교해야 한다.

for start in range(len(programs[0]) - K + 1):
    virus = programs[0][start:start + K]
    flag = False
    for v in virus:
        if ct[v] < N:
            flag = True
            break
    if flag: continue

start를 range(기준 프로그램(나는 첫번째 프로그램)의 길이 - K + 1) for문으로 하여금
start부터 길이가 K인 연속 부분 수열(이하 바이러스 후보)을 뽑아준다.
그리고 아까 설명했던 카운팅 최적화 방법을 써서, 바이러스 후보에 포함되어 있는 수가 만약 프로그램 수만큼 카운트가 되지 않았다면, 이 바이러스 후보는 바이러스가 될 수 없으므로 넘어간다.

그 다음은 바이러스 후보의 파이 함수를 만들어주자.
그런데 문제 지문을 보면 "단, 바이러스는 자신이 탐지되는 것을 막기 위해서, 자신의 코드를 반대로 기입하기도 한다." 라는 지문이 있다.
바이러스가 뒤집혀서 발견될 수 있다는 것이므로 바이러스 후보를 뒤집어서도 확인해야 한다.
그래서 먼저, 뒤집지 않은 바이러스 후보의 파이 함수를 만들어서 프로그램 전체와 KMP를 돌려주고, 그 다음, 뒤집은 바이러스 후보의 파이 함수를 만들어서 프로그램 전체와 KMP를 돌려주자.

여기서 최적화 하나 더!
뒤집은 바이러스 후보로 KMP를 돌릴 때에, 뒤집지 않은 바이러스 후보가 돌릴 프로그램에 이미 나타났다는 flag만 있으면 더 이상 확인해봐도 되지 않을 것이다. 그리고 각 프로그램 별로 코드가 나타났다는 flag가 있어야 나중에 YES를 출력할지 안할지 결정할 수 있으므로 그 flag를 이용하여 꼭 최적화를 해주자.

이것말고는 뭐.. 평범한 KMP.

코드

import sys; input = sys.stdin.readline

N, K = map(int, input().split())

ct = [0] * 10001 # 수가 나오는 횟수를 체크
programs = []
for _ in range(N):
    input()
    program = list(map(int, input().split()))
    programs.append(program)
    for p in program:
        ct[p] += 1

# 프로그램 하나를 기준으로 잡고 바이러스 후보를 만들기
for start in range(len(programs[0]) - K + 1):
    virus = programs[0][start:start + K]
    flag = False
    for v in virus:
        if ct[v] < N:   # 만약 바이러스 후보 안 수가 프로그램 수보다 적게 카운트 됐다면
            flag = True # 이 바이러스 후보는 바이러스가 될 수 없다.
            break
    if flag: continue

    result = [True] + [False] * (N - 1) # 바이러스 후보가 각 프로그램에 나타났는지 확인
    for V in [virus, virus[::-1]]:
        # 파이 함수 만들기
        pi = [0] * K
        i = 0
        for j in range(1, K):
            while i and V[i] != V[j]:
                i = pi[i - 1]
            if V[i] == V[j]:
                i += 1
                pi[j] = i
        # KMP
        # 혹시 이미 바이러스 후보가 나타났으면 패스
        for p in range(1, N):
            if result[p]: continue
            program = programs[p]
            P = len(program)
            i = 0
            for j in range(P):
                while i and V[i] != program[j]:
                    i = pi[i - 1]
                if V[i] == program[j]:
                    if i == K - 1:
                        result[p] = True
                        break
                    i += 1
    # 바이러스 후보가 모든 프로그램에 나타났는지 확인
    for r in result:
        if not r:
            break
    else:
        print('YES')
        exit()
# 모든 바이러스 후보가 바이러스가 아니었다면 for문이 끝나게 되고 마지막엔 NO 출력
print('NO')

여담

내가 Python3 1등이다. 푸하핳ㅎ
한 달 전에 제출 했던 코드도 136ms로 1등이었는데, sys.stdin.readline를 안했길래 방금 넣어서 제출해보니깐 8ms 단축.

파이썬을 공부하면서 느끼는건데, 점점 최적화하는 실력이 늘어난다. 파이썬은 워낙 무거운 아이이기 때문에 뭐만 하면 시간 초과가 나... 우씌!