코드 복사/붙여넣기 하는 당신이 아름답습니다.

15770 : QueryreuQ

풀이

문자열의 끝 문자가 추가 되거나 삭제 될 때, 매번의 추가/삭제 이후에 모든 부분 팰린드롬의 개수를 빠르게 구해야 한다.

문자가 추가/삭제 된다는 조건과 쿼리 문제라는 생각에 뭔가 어려워 보인다.

문자가 끝에서만 추가되고 삭제되기 때문에, 그냥 fix된 문자열에서 다이나믹으로 팰린드롬 구하는 O(n^2) 알고리즘을 그대로 가져오면 된다.

시간 제한이 1초여서 조금 빡빡한 듯 하지만, 엄밀히 따져보면 10000^2에 나누기 상수가 붙어서 1초 보다 좀 덜 돈다. (그리고 컴파일러 -o2 최적화가 붙으면 간단한 10000^2정도는 1초에 충분히 돌아가기도 한다)

O(4 * n^2)으로 짜면 시간 초과가 (아마?) 날 거고, 나는 다음과 같이 풀었다:

chk[i][j] = i번째 문자부터 j번째 문자까지가 팰린드롬인지 여부

chk[i][j] = 1 && str[i-1] = str[j+1] => chk[i-1][j+1] = 1

이런 느낌으로, 정확히는 코드를 보는 게 이해하기 더 좋을 것 같다.

사실 내 코드는 chk[i][j] = i번째 문자부터 i+j번째 문자까지가 팰린드롬인지 여부로 되어있는데, 어쩌다가 풀다 보니 그렇게 됐는데 고치기 귀찮아서 그냥…

나와 같은 방법으로 풀 것이라면, '-'가 들어왔을 때 chk 배열 초기화에 유의하자.

코드

#include <cstdio>

int q, len, dp[10003];
char c, str[10003];
bool chk[10003][10003];

int main() {
    scanf("%d ", &q);
    while (q--) {
        scanf("%c", &c);

        if (c == '-') {
            dp[len] = 0;
            for (int i = 1; i < len; i++) {
                chk[i][len-i] = chk[len][i] = 0;
            }
            printf("%d ", dp[--len]);
            continue;
        }

        str[++len] = c;
        dp[len] = dp[len-1] + 1;
        chk[len][0] = 1;
        if (str[len-1] == c) {
            dp[len]++;
            chk[len-1][1] = 1;
        }
        for (int i = 2; i < len; i++) {
            if (!chk[i][len-i-1] || str[i-1] != c) {
                continue;
            }
            dp[len]++;
            chk[i-1][len-i+1] = 1;
        }

        printf("%d ", dp[len]);
    }

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-11-28 11:28

Read more posts by this author