글 읽기 - 왜 시간초과가 나는지 모르겠습니다. (java)

willook 4년 전 0

문제를 푸는데 시간초과가 납니다.

제가 구현한 방식은 주어진 입력 조건은 그래프처럼 보고 DFS 방식으로 주어진 문자열에서 시작해서 소문자 문자열이 나타날때까지 탐색한 다음 나타난 소문자 문자열과 패턴 p를 비교하고 어디까지 비교했는지를 인자와 리턴 값으로 계속 넘기면서 구현했습니다.

또한 제가 생각한 제 구현의 시간복잡도는 다음과 같습니다.

최악의 경우가 잘 예측이 되지 않지만 A = B + C의 형태가 250(n)개, A = a 형태가 250(m)개가 나오는 경우라고 생각합니다.

제가 계산한 시간복잡도는 각 단어들을 리프까지 탐색하는데 O(n) 이 걸립니다.

탐색 결과 만들어지는 문자열의 최대 길이는 5*(n+1)일 테고 패턴 p와 선형적으로 비교하므로 마찬가지로 O(n)이 걸립니다.

따라서 걸리는 최종 시간복잡도는 O(n)이라고 생각합니다. (k=n+m)

제가 생각한 시간복잡도에서는 시간초과가 나는 이유를 잘모르겠습니다.

혹시 제가 구현한 부분 중 잘못된 부분이나 시간복잡도를 잘못 계산한 부분을 잘 모르겠습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	static StringBuilder sb = new StringBuilder();

	static void solve(String s1, String s2) {
		int idx = get(s1,s2,0);
		//idx가 s2의 끝까지 갔다면 성공
		if(idx == s2.length()) sb.append("YES\n");
		else sb.append("NO\n");
	}
	//ci는 s2의 현재 검사하고 있는 인덱스를 저장
	static int get(String s1, String s2, int ci) {
		//이미 ci가 끝까지 같다면 더이상 볼필요 없이 리턴
		if(ci==s2.length()) return ci;
		//s1이 소문자 문자열이라면 s2와 일치하는 부분을 검사
		if(s1.charAt(0)>='a' && s1.charAt(0)<='z') {
			for(int i=0;i<s1.length();i++) {
				if(ci != s2.length()) break;
				if(s1.charAt(i) == s2.charAt(ci))
					ci += 1;
			}
			return ci;
		}
		//s1을 map1 또는 map2에서 값을 꺼내 다음 get을 호출
		if(map1.containsKey(s1)) 
			return get(map1.get(s1),s2,ci);
		Var var = map2.get(s1);
		ci = get(var.s1,s2,ci);
		ci = get(var.s2,s2,ci);
		return ci;
	}
	//START = FIRST + SECND의 변수에서 FIRST, SECND를 저장하기 위한 클래스
	static class Var{
		String s1, s2;
		Var(String s1, String s2){
			this.s1 = s1;
			this.s2 = s2;
		}
	}
	//D = good 형태의 변수를 저장
	static HashMap<String, String> map1;
	//START = FIRST + SECND 형태의 변수를 저장
	static HashMap<String, Var> map2;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int TC = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < TC; tc++) {
			map1 = new HashMap<String, String>();
			map2 = new HashMap<String, Var>();
			int n = Integer.parseInt(br.readLine());
			for(int i=0;i<n;i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				String left = st.nextToken();
				st.nextToken();
				String right1 = st.nextToken();
				//더이상의 토큰이 없다면 D = good형태의 입력으로 판단
				if(!st.hasMoreTokens()) {
					map1.put(left, right1);
				}
				else {
					st.nextToken();
					String right2 = st.nextToken();
					map2.put(left, new Var(right1, right2));
				}
			}
			String s1 = br.readLine();
			String s2 = br.readLine();
			solve(s1,s2);
		}
		System.out.print(sb);
	}
}

chogahui05 4년 전 0

이렇게 간단하게 풀리면 어려울 리가 없습니다.

playsworld16 8달 전 0

이 문제는 상당히 어려운 문제입니다.

탐색 결과 만들어지는 문자열의 최대 길이는 5*(n+1) 라고 하셨는데, 이보다 훨씬 긴 문자열을 만들 수 있습니다.

A = B + B

B = C + C

C = D + D

...

YYY = ZZZ + ZZZ

ZZZ = abcde

대충 이런식으로 500줄을 채우면, 5*2^499 의 길이의 문자열이 만들어집니다.

이걸 전부 탐색하면 당연히 시간초과가 나겠죠? 전부 탐색하지 않는 다른 방법을 생각해내셔야 합니다.

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

문제

문제

출처

ICPC

왜 시간초과가 나는지 모르겠습니다. (java)

willook 4년 전 0

chogahui05 4년 전 0

playsworld16 8달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말