[백준] 1701 Cubeditor

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

KMP 알고리즘으로 접근하여 주어진 문자열에서 가능한 패턴을 추출하여 2번 이상 포함되는 경우를 반환하도록 접근하였습니다.

그러나 제한시간을 초과하여 KMP 알고리즘을 이용할때 사용하는 접두사와 접미사가 일치하는 길이를 저장하는 테이블로 접근하였습니다.

 

이 테이블은 접두사와 접미사가 어느 길이로 일치하는지 저장하는 테이블로, 특정 패턴(접두사)이 문자열의 가장 뒤쪽(접미사)와 일치하므로 문장에 패턴이 두번 이상 나오게 되어 문제의 조건에 부합합니다.

그리하여 테이블의 값에서 가장 큰 값을 반환하도록 하였습니다. 

2) 알고리즘

• KMP

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

def make_table(pattern):                            # KMP에서 이용되는 접두사와 접미사가 일치하는 길이를 저장하는 테이블 구하기
    global answer

    table = [0] * len(pattern)                      # 테이블 초기화

    j = 0                                           # 접두사 인덱스
    for i in range(1, len(pattern)):                
        while j > 0 and pattern[i] != pattern[j]:   # 접두사 인덱스의 문자와 가장 마지막 문자가 일치하지 않으면
            j = table[j-1]                          # 테이블에 저장된 인데스로 값 변경
        
        if pattern[i] == pattern[j]:                # 문자가 일치하면
            j += 1                                  # 접두사 인덱스 증가
            table[i] = j                            # 일치하는 길이 저장
    
    answer = max(answer, max(table))

s = sys.stdin.readline().rstrip()   # 입력 받은 문자열
answer = 0                          # 정답 변수

i = 0                               # 가장 앞에서부터 시작
while i < len(s) - (answer*2):      # 확인할 문자가 정답의 길이보다 짧다면 확인할 필요가 없음
    make_table(s[i:])               # KMP 알고리즘에서 사용하는 접두사 접미사가 일치하는 길이 저장하는 테이블 구함
    i += 1

print(answer)

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

KMP 알고리즘을 사용해 그 패턴이 문자열에 존재하는지 찾는 방식은 시간 초과 발생하여, 이 문제 해결을 위해 다른 방식을 찾는 과정이 어려웠습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://www.acmicpc.net/problem/1701

1701번: Cubeditor

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다