## ID : OCR 자바 시간초과 질문

• aka2344

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

import java.io.BufferedReader;
import java.io.BufferedWriter;
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
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;
}
}


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