`
처음에 시간초과가 나서 위치 메모이제이션을 해주어서 통과. 그래도 1000ms 정도 나옴..
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static String a,b,c;
static int N,as,bs,cs;
static boolean flag;
static boolean visit[][][];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
N = Integer.parseInt(br.readLine());
for (int i = 1; i <= N; i++) {
sb.append("Data set ").append(i).append(": ");
st = new StringTokenizer(br.readLine());
a = st.nextToken();
b = st.nextToken();
c = st.nextToken();
as = a.length();bs = b.length();cs=c.length();
visit = new boolean[as+1][bs+1][cs+1];
flag = false;
solve(0,0,0);
sb.append(flag?"yes":"no").append("\n");
}
System.out.println(sb);
}
private static void solve(int i, int j,int cnt) {
if (flag) return;
if(cnt==cs) {
flag = true;
return;
}
// 해당 위치 이미 탐색한 경우
if(visit[i][j][cnt]) return;
// a와 b 비교하여 문자열 탐색
if(i<as && a.charAt(i)==c.charAt(cnt)) {
visit[i][j][cnt] = true;
solve(i+1,j,cnt+1);
}
if(j<bs &&b.charAt(j)==c.charAt(cnt)) {
visit[i][j][cnt] = true;
solve(i,j+1,cnt+1);
}
}
}
|
아래는 좀 더 효율적으로 짜보려고 수정한 코드이다. 우선 생각해보니 방문체크는 2차원으로 충분했다.
그리고 문자열 비교하기 전에 방문체크를 하고 함수를 boolean으로 하여 return했더니 시간이 줄었다. c에 a와 b에 해당하는 문자가 없을 경우 위의 코드에선 방문체크를 하지 않아서 그런 것 같다…
이렇게 하니 160정도 나왔다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class B9177 {
static String a,b,c;
static int N,as,bs,cs;
static boolean visit[][];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
N = Integer.parseInt(br.readLine());
for (int i = 1; i <= N; i++) {
sb.append("Data set ").append(i).append(": ");
st = new StringTokenizer(br.readLine());
a = st.nextToken();
b = st.nextToken();
c = st.nextToken();
as = a.length();bs = b.length();cs=c.length();
visit = new boolean[as+1][bs+1];
sb.append(solve(0,0,0)?"yes":"no").append("\n");
}
System.out.println(sb);
}
private static boolean solve(int i, int j,int cnt) {
if(cnt==cs) return true;
if(visit[i][j]) return false;
visit[i][j] = true;
boolean flag = false;
if(i<as && a.charAt(i)==c.charAt(cnt))
flag|=solve(i+1,j,cnt+1);
if(j<bs &&b.charAt(j)==c.charAt(cnt))
flag|=solve(i,j+1,cnt+1);
return flag;
}
}
|