https://www.acmicpc.net/problem/5582
처음 문제를 풀었을 때는 단순하게 String라이브러리의 substring()
과 contains()
메서드를 활용하여 가장 긴 문자열부터 하나씩 비교를 하며 풀이를 하였습니다. 그렇게 풀이를 한 결과 주어진 테스트케이스와 질문하기의 추가 케이스들은 모두 통과를 하나 실제 테스트에서는 통과를 하지 못하였습니다...제가 놓친 무언가가 있는 것 같은데 그것이 무엇인지 모르겠네요😥😥
그리하여 Dynamic programming방식으로 처음부터 문제를 다시 풀이하였습니다.
그 결과 아래와 같이 통과를 하는 결과를 얻을 수 있었습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1 = br.readLine();
String str2 = br.readLine();
if (str1.length() < str2.length()) {
System.out.println(findResult(str1, str2));
}
else {
System.out.println(findResult(str2, str1));
}
}
private static int findResult(String str1, String str2) {
for (int i = str1.length(); i > 0; i--) {
int start = 0;
int end = start + i;
while (end <= str1.length()) {
if (str2.contains(str1.substring(start, end))) {
return i;
}
start += i;
end += i;
}
}
return 0;
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1 = br.readLine();
String str2 = br.readLine();
int[][] dp = new int[str1.length()+1][str2.length()+1];
int max = 0;
for (int i = 1; i <= str1.length(); i++) {
for (int j = 1; j <= str2.length(); j++) {
if (str1.charAt(i-1) == str2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] +1;
}
if (dp[i][j] > max) max = dp[i][j];
}
}
System.out.println(max);
}
}