개발자 톡
실행시간 줄일만한 부분 좀 찾아주실 수 있으신가요?
- 등록일
- 2025-02-20 14:08:12
- 조회수
- 16
- 작성자
- mookryong04
테케 4번, 19번에서 0.1초 오버되어서 시간 초과 뜨는데
어디서 줄일 수 있을지 감이 안잡히네요 ㅠㅠ
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;
public class Main {
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static StringTokenizer st;
public static ArrayList<String> results;
public static int[][] dp;
public static char map[][];
static int n;
public static int visitied[][];
public static void main(String[] args) throws IOException , Exception{
// TODO Auto-generated method stub
int temp1;
int temp2;
char temp3;
//트리 문제
st = new StringTokenizer(br.readLine());
//간선개수 n
n = Integer.parseInt(st.nextToken());
//문자열 길이 m
int m = Integer.parseInt(st.nextToken());
//할아버지가 좋아하는 루트 gRoute
String gRoute = br.readLine();
//System.out.println("gRoute : "+gRoute);
//맵 객체 선언 n+1
map = new char[n+1][n+1];
//n-1만큼 루프해서 값 받기
for(int i=0; i<n-1; i++)
{
st = new StringTokenizer(br.readLine());
temp1=Integer.parseInt(st.nextToken());
temp2=Integer.parseInt(st.nextToken());
temp3=st.nextToken().charAt(0);
map[temp1][temp2] = temp3;
map[temp2][temp1] = temp3;
}
//총 결과들이 저장될 results
results = new ArrayList<String>();
visitied = new int[n+1][n+1];
dfs(1, "");
int maxVal = 0;
int chkVal = 0;
for(int i=0; i<results.size(); i++)
{
//System.out.println("체크할 값 : "+results.get(i));
chkVal = LCS(gRoute, results.get(i));
//System.out.println("체크 결과 : "+chkVal);
if(maxVal < chkVal)
maxVal=chkVal;
}
System.out.println(maxVal);
}
private static void dfs(int right, String fullString) {
// TODO Auto-generated method stub
//시작 : 현재 값을 fullString에 추가
//탈출조건 : 더 찾을 노드가 없음
if(map[right].toString().equals(""))
{
results.add(fullString);
return;
}
int tal =0;
for(int i=1; i<n+1; i++)
{
if(map[right][i] != 0 && visitied[right][i] ==0)
{
tal++;
}
}
if(tal ==0)
{
results.add(fullString);
return;
}
//재귀조건 : 찾을 노드가 있음
for(int i=1; i<n+1; i++)
{
if(map[right][i] != 0 && visitied[right][i] ==0)
{
//다음 노드 값, 문자열에 값 추가
visitied[right][i] = 1;
visitied[i][right] = 1;
dfs(i, fullString + map[right][i]);
}
}
}
public static int LCS(String a, String b) {
int dp[][] = new int[a.length() + 1][b.length() + 1];
for (int i = 1; i <= a.length(); i++) {
for (int j = 1; j <= b.length(); j++) {
if (a.charAt(i-1) == b.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[a.length()][b.length()];
}
}