의식의 흐름
이차원 배열 만들어서 하나씩 비교하면서 가능한 수를 저장하면 될 것 같은데...?
(글자 수 = 최대 1000개 => 1000*1000 => 시간 가능)
풀이 과정
1. 첫째불과 둘째줄에 입력 받은 문자열을 각각 배열(input1, input2)에 저장한다.
-> 지금 생각해보니 문자열을 굳이 배열에 저장안하고 나중에 .charAt() 써도 됐을듯하다.
2. input1[j]와 input2[i]를 비교하여 배열(dp)에 가능한 부분 수열의 최대 길이를 담는다.
- 두 값이 같은 경우, dp[j+1][i+1] = dp[j][i]+1;
- 두 값이 다른 경우, dp[j+1][i+1] = Math.max(dp[j+1][i], dp[j][i+1]);
3. input1, input2의 모든 문자에 대해 2번 과정을 반복한다.
4. 2번-3번 과정에서 나온 dp[][]의 값 중 최대값(max)이 가능한 부분 수열의 최대 길이이므로 이를 출력한다.
코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
public static int[][] dp;
public static int max = 0;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] input1 = br.readLine().split("");
String[] input2 = br.readLine().split("");
dp = new int[input2.length+1][input1.length+1];
for(int i=0;i<input1.length;i++){
for(int j=0;j<input2.length;j++){
if(input1[i].equals(input2[j])){
dp[j+1][i+1] = dp[j][i]+1;
max = Math.max(dp[j+1][i+1], max);
}
else{
dp[j+1][i+1] = Math.max(dp[j+1][i], dp[j][i+1]);
}
}
}
bw.write(Integer.toString(max));
bw.flush();
br.close();
bw.close();
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[JAVA] 백준 q2631 - 줄세우기 (2) | 2023.10.26 |
---|---|
[JAVA] 백준 q9084 - 동전 (0) | 2023.10.25 |
[JAVA] 백준 q15724 - 주지수 (2) | 2023.10.23 |
[JAVA] 백준 q1607 - 숨바꼭질 (2) | 2023.10.20 |
[JAVA] 백준 q15486 - 퇴사2 (0) | 2023.10.19 |