이 문제를 조금 특이한 방법으로 푼 것 같아서 풀이를 올려봅니다.
코드
def solve(s):
L = len(s)
cur_idx = 1
piece_length = 1
cur_compared = 0
while cur_idx < L:
if s[cur_idx] == s[cur_compared]:
cur_compared += 1
cur_idx += 1
continue
# 만약 절반 이상에서 틀렸다면
# 더 이상은 조각의 길이를 늘려도 의미가 없다.
if cur_idx > L // 2:
piece_length = L
break
if cur_compared > 0:
cur_compared -= 1
else:
cur_idx += 1
piece_length += 1
# 끝까지 비교했는가.
if cur_compared % piece_length == 0:
print(L // piece_length)
else:
print(1)
while True:
s = input()
if s == '.':
break
solve(s)풀이
결국 이 문제는 같은 조각 몇개로 string을 나눌 수 있는가로 정의할 수 있다.
piece_length는 현재 조각의 길이, cur_compared는 비교할 조각의 문자 위치이다. 현재 인덱스의 문자와 s[cur_compared]를 비교해 같다면, 조각의 다음 문자와 다음 인덱스의 문자를 비교한다.
만약 다르다면 3가지 경우가 있다.
-
cur_compared가 0 이상이라면, 앞의 탐색한 문자를 조각에 포함시키고cur_compared를 1 줄여서 다시 현재 문자와 비교합니다. -
cur_compared가 0이라면 현재 문자를 조각에 포함 시킨다. -
만약 다르고 현재 인덱스가 절반 이상이라면 더 이상 조각의 길이를 늘려 탐색을 해도 의미가 없으므로 조각 길이를 L로 만들고(= 조각의 개수 1개) 탐색을 종료한다.
탐색을 종료한 후 cur_compared의 길이와 조각의 길이를 나눠 떨어진다면 끝까지 비교한 것이므로 s의 길이 // 조각의 길이가 정답.
아니라면 조각으로 나눠지지 않으므로 1이 정답.
최악의 경우 s의 길이만큼 반복이 돌아가므로 시간 복잡도는 O(N)이다.
예시
간단한 예시입니다. 조각에서 볼드 처리된 부분을 cur_compared라고 생각하면 됩니다.
s = 'abaaba'일때.
1. 조각 = 'a' 현재 문자 = 'b'(1) / 조각의 비교 문자와 현재 문자가 일치하지 않고 cur_compared가 0이므로 현재 문자를 조각에 포함시킴.
2. 조각 = 'ab' 현재 문자 = 'a'(2) / 조각의 비교 문자와 현재 문자가 일치하므로 다음 문자 탐색.
3. 조각 = 'ab' 현재 문자 = 'a'(3) / 조각의 비교 문자와 현재 문자가 일치하지 않고 cur_compared가 1이므로 이전 'a'(2)를 조각에 포함시킨다.
4. 조각 = 'aba' 현재 문자 = 'a'(3) / 조각의 비교 문자와 현재 문자가 일치하므로 다음 문자 탐색.
5. 조각 = 'aba' 현재 문자 = 'b'(4) / 조각의 비교 문자와 현재 문자가 일치하므로 다음 문자 탐색.
6. 조각 = 'aba' 현재 문자 = 'a'(5) / 조각의 비교 문자와 현재 문자가 일치하므로 다음 문자 탐색.
7. 탐색이 끝났고, 현재 탐색한 문자의 길이와 조각의 길이가 같으므로 s의 길이 // 조각의 길이가 정답.
코멘트
- 1등해서 기분이 좋다.
- 조각을 패턴으로 바꾸면 그냥 kmp인가...? 아직 공부가 모자라서 잘 모르겠다. kmp를 응용하긴 한듯.
