[백준][문자열] Cubeditor

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

1701번: Cubeditor

 

내가 작성한 코드

# 시간 초과

import sys
from collections import defaultdict
read = sys.stdin.readline

s = "a" * 5000
dic = defaultdict(list)

for i, c in enumerate(s):
    dic[c].append(i)

cnt = 0
while dic:
    cnt += 1
    nw_dic = defaultdict(list)
    for c, arr in dic.items():
        if len(arr) <= 1:
            continue
        for i in arr:
            if i+1 >= len(s):
                continue
            nw_dic[c + s[i+1]].append(i+1)
    dic = nw_dic

print(cnt-1)

• 각 알파벳 set의 인덱스를 리스트로 저장
• 문제 조건이 "2개 이상"이므로, 리스트의 요소가 2개 이상인 key만 다음 인덱스의 알파벳 확인

다른 사람이 작성한 코드

import sys
read = sys.stdin.readline

def make_table(s: str) -> list[int]:
    table = [0] * len(s)
    j = 0
    for i in range(1, len(s)):
        c = s[i]
        while j > 0 and s[j] != c:
            j = table[j-1]

        if s[j] == c:
            j += 1
            table[i] = j
    return table

s = read().rstrip()
answer = 0
for i in range(len(s)):
    answer = max(answer, max(make_table(s[i:])))
print(answer)

• prefix와 중복된 char 개수를 저장하는 KMP 알고리즘 활용
• 모든 prefix 패턴을 확인해야하므로, 문자열을 앞에서부터 len만큼 줄여가면서 KMP 적용

https://peisea0830.tistory.com/65

[Python 3] BOJ - 1701 "Cubeditor"

 

기억해야할 것

• 내가 작성한 코드는 97% 정도에서 시간 초과다
  
  • "a" * 5000과 같이, 트리 구조로 생각할 때 최악의 구조일 경우 매우 느림
  • 이 경우, O(n^2)
• KMP도 O(n^2)인데 어떤 차이인지 모르겠음
  • dictionary에 의한 탐색 때문은 아닌듯(key가 "a" 뿐이고, 이도 해시 테이블이라 바로 찾을텐데...)
  • dictionary를 매 loop마다 새로 만들어서 그런지?
• 우선 KMP 잘 활용하자
  • 결론적으로 더 빠르기 때문에 활용을 해야할 듯