글 읽기 - 50%대에서 시간초과가 납니다

imds39 6년 전 0

50%대에서 시간초과에러가 발생하는데.. 어디서 시간을 줄여야 하는건지 잘 모르겠습니다! 도와주세요!

일단, KMP랑 비슷하게 INDEX, COUNT 배열을 두었습니다.

INDEX 배열에는 패턴이 Sequential하게 오는 최대길이를 저장합니다.

다음에 i길이 text에서 s길이 패턴을 검사할때 이 값을 이용하여 건너뜁니다.

COUNT 배열에는 패턴이 Sequential하게 올 때, 그 갯수(주기)를 저장합니다.

다음에 i길이 text에서 s길이 패턴을 검사할때 INDEX 배열을 이용하여 비교인덱스를 건너뛰게 되는데 그만큼 COUNT도 증가해야 하기 떄문입니다.

이런식으로 하면 비교하는 횟수를 줄일 수 있다고 생각했는데, 이게 전혀 틀린건지, 아니면 뭔가 빼먹은 부분이 있는지 궁금합니다!

package bj03779;

import java.io.*;

/**
 * Created by dasom on 2017-09-21.
 */
public class Main {
    private static int[] INDEX;
    private static int[] COUNT;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader(new File("BaekJoon\\src\\bj03779\\input.txt")));
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N;
        int tcNo = 1;
        while ((N = Integer.parseInt(br.readLine())) != 0) {
            System.out.println("Test case #" + tcNo++);
            char[] textChars = br.readLine().toCharArray();
            INDEX = new int[N];
            COUNT = new int[N];
            for (int textLen = 2; textLen <= N; textLen++) {
                getMaxCountSequencialPattern(textChars, textLen);
            }
            System.out.println();
        }
    }

    private static void getMaxCountSequencialPattern(char[] textChars, int textLen) {
        int maxCount = -1;
        for (int patternLen = 1; patternLen < textLen; patternLen++) {

            if (textLen % patternLen != 0) {
                continue;
            }
            if (COUNT[patternLen - 1] == -1) {
                continue;
            }

            int patternIndex = 0;
            int count = COUNT[patternLen - 1];
            boolean isSequential = true;
            for (int baseIndex = INDEX[patternLen - 1]; baseIndex < textLen; baseIndex++) {
                if (textChars[baseIndex] == textChars[patternIndex]) {
                    if (patternIndex + 1 == patternLen) {
                        patternIndex = 0;
                        count++;
                    } else {
                        patternIndex++;
                    }
                } else {
                    isSequential = false;
                    break;
                }
            }
            if (isSequential) {
                INDEX[patternLen - 1] = textLen;
                COUNT[patternLen - 1] = count;
                if (count > maxCount) {
                    maxCount = count;
                }
            } else {
                INDEX[patternLen - 1] = -1;
                COUNT[patternLen - 1] = -1;
            }
        }
        if (maxCount != -1) {
            System.out.println(textLen + " " + maxCount);
        }
    }
}

sgchoi5 6년 전 0

seerc 문제는 대회에서 사용했던 TC 가 공개되어 있으니 한 번 써보세요..

http://gooddaytocode.blogspot....

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

50%대에서 시간초과가 납니다

imds39 6년 전 0

sgchoi5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말