ID : OCR 자바 시간초과 질문

  • aka2344
    aka2344

    OCR 문제를 자바로 풀었습니다.
    종만북 알고리즘대로 구현하였고, 테스트 케이스도 잘 통과하여
    문제가 없어보이는데, 자꾸 시간초과로 채점됩니다.
    입력성능을 위해 BufferReader를 사용하여 배열 성분들을
    각각 읽어들였는데, 무엇이 문제인가요??

    문제링크 : https://www.algospot.com/judge/problem/read/OCR

    import java.io.BufferedReader;
    import java.io.BufferedWriter;
    import java.io.InputStreamReader;
    import java.io.OutputStreamWriter;
    import java.util.StringTokenizer;
    
    public class Main {
    
        static double[][] cache;
        static int m;
        static int q;
        static String words[];
        static double B[];
        static double T[][];
        static double M[][];
        static int[] S;
        static int[][] choice;
        static int n;
    
        public static void main(String[] args) throws Exception {
            // TODO Auto-generated method stub
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            m = Integer.parseInt(st.nextToken());
            q = Integer.parseInt(st.nextToken());
            words = new String[m+1];
            B = new double[m+1];
            T = new double[m+1][m+1];
            M = new double[m+1][m+1];
            int i = 1;
            st = new StringTokenizer(br.readLine(), " ");
            while (st.hasMoreTokens()) {
                words[i++] = st.nextToken();
            }
            i = 1;
            st = new StringTokenizer(br.readLine(), " ");
            while (st.hasMoreTokens()) {
                B[i++] = Math.log(Double.parseDouble(st.nextToken()));
            }
            for (int j = 0; j <= m; j++) {
                i = 1;
                if(j==0) {
                    for(;i<=m;i++) {
                        T[j][i] = B[i];
                    }
                }
                else {
                    st = new StringTokenizer(br.readLine(), " ");
                    while (st.hasMoreTokens()) {
                        T[j][i++] = Math.log(Double.parseDouble(st.nextToken()));
                    }
                }
            }
            for (int j = 1; j <= m; j++) {
                i = 1;
                st = new StringTokenizer(br.readLine(), " ");
                while (st.hasMoreTokens()) {
                    M[j][i++] = Math.log(Double.parseDouble(st.nextToken()));
                }
            }
            for (int j = 0; j < q; j++) {
                cache = new double[102][502];
                choice = new int[102][502];
                for (int a = 0; a < 102; a++) {
                    for (int b = 0; b < 502; b++) {
                        cache[a][b] = 1;
                    }
                }
                st = new StringTokenizer(br.readLine(), " ");
                n = Integer.parseInt(st.nextToken());
                S = new int[n];
                i = 0;
                while (st.hasMoreTokens()) {
                    String s = st.nextToken();
                    for (int t = 1; t <= m; t++) {
                        if (words[t].equals(s))
                            S[i++] = t;
                    }
                }
                OCR(0, 0);
                bw.write(reconstruct(0, 0) + "\n");
                bw.flush();
            }
            bw.close();
    
        }
    
        static double OCR(int idx, int prev) {
            if (idx == n)
                return 0;
            double ret = -1e200;
            int wid = S[idx];
            if (cache[idx][prev] != 1) {
                return cache[idx][prev];
            }
            for (int i = 1; i <= m; i++) {
                double temp = T[prev][i] + M[i][wid] + OCR(idx + 1, i);
                if (temp > ret) {
                    ret = temp;
                    cache[idx][prev] = ret;
                    choice[idx][prev] = i;
                }
            }
            return ret;
    
        }
    
        static String reconstruct(int idx, int prev) {
            int ch = choice[idx][prev];
            String ret = words[ch];
            if (idx < n - 1)
                ret = ret + " " + reconstruct(idx + 1, ch);
            return ret;
        }
    }
    

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