COUNTPALIN 시간초과 자꾸 뜨네요

  • sw.maeng
    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++;
    }

    l = i - 1;
        r = i + 1;
        while (str[l] == str[r] && 0 <= l && r < len) {
            sumPalin++;
            l--;
            r++;
        }
    }
    return sumPalin;

    }


    7년 전
2개의 댓글이 있습니다.
  • sukh1222
    sukh1222

    이문제 O(n)에 가능합니다.


    7년 전 link
  • sw.maeng
    sw.maeng

    역시; 그렇군요.. 감사합니다. 더 고민해봐야겠네요


    7년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.