COUNTPALIN 문제 자꾸 시간초과가 뜨네요
주어진 문장안에 있는 모든 회문을 찾아 갯수를
리턴하는 문제입니다.
제가 생각한 방법은 문장의 각 문자를 기준으로
aa 처럼 짝수개가 되는 것과
aba 처럼 홀수개가 되는 것을
양쪽으로 확장해 가면서 회문을 이루는 갯수를
세어 나가는 방법입니다.
이 방법은 대략 O(2N^2) 정도 나오겠네요.
설마 이문제 O(N) 에 가능한가요??
아래는 제 실패한 코드입니다... **구현한 함수 **
int getPalinCount(char* str, int len) {
int sumPalin = 0;
int l, r;
for (int i = 1; i < len; ++i) {
l = i - 1;
r = i;
while (str[l] == str[r] && 0 <= l && r < len) {
sumPalin++;
l--;
r++;
}
l = i - 1;
r = i + 1;
while (str[l] == str[r] && 0 <= l && r < len) {
sumPalin++;
l--;
r++;
}
}
return sumPalin;
sw.maeng
COUNTPALIN 문제 자꾸 시간초과가 뜨네요
주어진 문장안에 있는 모든 회문을 찾아 갯수를
리턴하는 문제입니다.
제가 생각한 방법은 문장의 각 문자를 기준으로
aa 처럼 짝수개가 되는 것과
aba 처럼 홀수개가 되는 것을
양쪽으로 확장해 가면서 회문을 이루는 갯수를
세어 나가는 방법입니다.
이 방법은 대략 O(2N^2) 정도 나오겠네요.
설마 이문제 O(N) 에 가능한가요??
아래는 제 실패한 코드입니다...
**구현한 함수 **
int getPalinCount(char* str, int len) {
int sumPalin = 0;
int l, r;
for (int i = 1; i < len; ++i) {
l = i - 1;
r = i;
while (str[l] == str[r] && 0 <= l && r < len) {
sumPalin++;
l--;
r++;
}
}
11년 전