(백준 알고리즘 문제풀이) 1701번 Cubeditor
by 줌코딩
문제
문제 접근
- 이 문제를 어떻게 KMP로 풀지를 고민하다가 2시간 만에 방법이 퍼뜩 떠올랐다.
- 2번 이상 존재한다는 것은 부분 문자열 중에 접두사와 접미사가 같은 경우가 있다는 것이고 이 접두사와 접미사가 제일 길게 같은 경우가 정답이라고 볼 수 있다.
- 즉, KMP에서 찾아냈던 pi값이 가장 큰 경우가 정답이 된다.
- 여기서 문제는 기존의 make_pi 함수는 부분 문자의 시작은 0이지만 이번에는 0이 아니라 문자열의 처음부터 끝까지이다.
- 이를 위해 make_pi를 변형해서 답을 구했다.
코드
기존 make_pi()
void make_pi(){
int j = 0;
for(int i = 1; p[i] != '\0' ; i++){
while(j > 0 && p[i] != p[j]) j = pi[j-1];
if(p[i] == p[j]) pi[i] = ++j;
}
}
정답 코드
#include <iostream>
using namespace std;
int ans, n, pi[5001];
char t[5001];
int main(){
cin.sync_with_stdio(false); cin.tie(NULL);
cin >> t;
for(int i = 0; t[i] != '\0'; i++){
int k = 0;
for(int j = i + 1; t[j] != '\0'; j++){
while(k > 0 && t[j] != t[i + k]) k = pi[k - 1];
if(t[j] == t[i + k]){
k++;
if(ans < k)ans = k;
}
pi[j - i] = k;
}
}
cout << ans;
}
느낀점
- 아무래도 정확하게 개념을 이해하지 못하고 있었는지 접두사를 바꾸는 것만으로도 큰 어려움을 겪었다.(제출만 20번 넘게 했다.)
- 내가 표현하고자 하는 것이 뭔지 정확히 적고나니 문제점을 찾을 수 있었다.
- 막 바꾸면서 제출하기보다는 천천히 line by line으로 생각하면서 구현해보자.
이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.
Subscribe via RSS