[Python 3] BOJ - 1701 "Cubeditor"

 # 문제 링크 : https://www.acmicpc.net/problem/1701

1701번: Cubeditor

 # 풀이 :

이 문제의 핵심은 failure 배열의 이해이다. 우선 failure 배열이 무엇인지 알기전에 문제의 설명에 대해 예시를 통해 이해해보자. 문제의 설명의 골자는 현재 어떤 문자열 s에서 2번 이상 나타나는 부분문자열 중 길이가 가장 긴 것의 길이를 출력하라는 것이다.

<그림 1. 문제의 tc>

<그림 2. 문제의 tc>

<그림 3. 문제의 tc>

 현재 그림 1은 길이가 1이고 최소 2번 이상 출현하는 부분 문자열의 경우이고 그림 2는 길이가 2이고 최소 2번 이상 출현하는 부분 문자열, 그림 3은 길이가 3이고 최소 2번 이상 출현하는 부분 문자열의 경우이다. 그런데 그림 1과 그림 2는 그림 3으로 설명이 된다.

 그런데 문제는 그림 1의 첫번째, 그림 2의 첫번째, 그림 3의 첫번째는 부분 문자열이 원래 문자열 s의 첫번째 문자부터 시작하고 있다. 또한 그림 1의 두번째, 그림 2의 두번쨰는 부분 문자열이 원래 문자열 s의 두번째 문자부터 시작하고 있다. 또 문제에서 원래 문자열 s는 주어졌지만 패턴에 해당하는 p는 주어지지 않았다. 그런데 그림 1부터 그림 3까지 보았을 때, 가능한 정답의 시작 문자가 다 달라질 수 있으므로 가능한 패턴은 맨 첫글자부터 하나하나씩 지워가는 문자들이 모두 패턴이 된다. 즉, abcdabcabb, bcdabcabb, cdabcabb, dabcabb, ... 의 형태로 패턴이 점점 줄어든다.

<그림 4. p = 'abcdabcabb'인 경우 (1)>

 

<그림 5. p = 'abcdabcabb'인 경우 (2)>

<그림 6. p = 'abcdabcabb'인 경우 (2)>

<그림 7. p = 'abcdabcabb'인 경우 (3)>

<그림 8. p = 'abcdabcabb'인 경우 (4)>

<그림 9. p = 'abcdabcabb'인 경우 (5)>

<그림 10. p = 'abcdabcabb'인 경우 (6)>

<그림 11. p = 'abcdabcabb'인 경우 (7)>

<그림 12. p = 'abcdabcabb'인 경우 (8)>

<그림 13. p = 'abcdabcabb'인 경우 (9)>

 그림 4부터 그림 13까지의 과정이 끝나면 [0,0,0,0,1,2,3,1,2,0]의 리스트가 리턴된다. 이때 각 원소들의 의미는 인덱스가 i까지인 패턴 내 부분 문자열에서 가장 좌측과(접두) 가장 우측(접미)이 최대로 같은 길이이다. 예를 들어 i가 5인 경우를 생각해보자. i가 5라면 패턴이 'abcdabcabb'이고 패턴 내 부분 문자열이 'abcdab'이다. 그런데 맨 왼쪽에서 오른쪽으로 2개의 문자열인 'ab'와 맨 오른쪽에서 왼쪽으로 2개의 문자열인 'ab'가 같다. 그런데 맨 왼쪽에서 오른쪽으로 3개인 문자열인 'abc'와 맨 오른쪽에서 왼쪽으로 3개인 문자열인 'dab'의 경우는 같지 않으므로 인덱스 5에서 원소의 값은 2가 된다.

 그런데, 결국 가장 왼쪽 기준에서 한번, 가장 오른쪽 기준에서 한번은 나와야 하므로 인덱스 i에서의 원소값은 반드시 최소 2번이상 나타나는 문자열이고, 정의에 따라 최대로 같은 길이이므로 정확히 문제에서 요구하는 조건을 만족한다. 따라서 원 문자열에 대한 가능한 모든 패턴(왼쪽으로 부터 한글자씩 이동)의 failure 배열을 구한 후 각 failure 배열의 최댓값을 구하면 문제의 정답을 구할 수 있다.

 

 # 코드

import sys

# failure : failure 배열을 리턴하는 함수
def failure(pattern):
    table = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        # i가 가리키는 문자와 j가 가리키는 문자가 다르다면
        # j - 1의failure로 j는 이동해야 한다
        # 어쨌든 현재 i와 j가 다르지만 j - 1까지의 비교는 완료되었기 때문이다
        while j > 0 and pattern[i] != pattern[j]:
            j = table[j - 1]
            
        # i가 가리키는 문자와 j가 가리키는 문자가 같다면
        # j를 1증가시키고 failure[i]의 값을 1 증가시킨다
        # 왜냐면 j는 0부터 j까지 문자열 중 가장 길게 매칭된 부분 패턴의 길이를 의미하기 때문이다
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
    return table

# 입력부
pat = sys.stdin.readline().rstrip()

ans = 0
for i in range(len(pat)):
    # 잠재적인 패턴이 될 수 있는 모든 패턴에 대하여 failure 배열을 얻은 후 최대값을 갱신한다
    ans = max(ans, max(failure(pat[i:])))
    
# 정답 출력
print(ans)