- 코드
정답 코드 : 기존 LCS 길이구하는 알고리즘 + dp배열을 통해 최장길이 문자열도 가져왔다. 문자열은 거꾸로가면서 같으면 추가해준 뒤 --, dp배열의 수가 x-1이 현재위치보다 값이 낮으면 x--, y-1이 현재위치보다 값이 낮으면 y--를 해주면서 반복문을 돌린다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String firstInput = br.readLine();
String secondInput = br.readLine();
int[][] dp = new int[firstInput.length() + 1][secondInput.length() + 1];
for (int i = 1; i <= firstInput.length(); i++) {
for (int j = 1; j <= secondInput.length(); j++) {
if (firstInput.charAt(i - 1) == secondInput.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
int x = firstInput.length();
int y = secondInput.length();
StringBuilder sb = new StringBuilder();
while(x != 0 && y != 0) {
if(firstInput.charAt(x-1) == secondInput.charAt(y-1)) {
sb.append(firstInput.charAt(x-1));
x--;
y--;
}
else if(dp[x][y] == dp[x-1][y])
x--;
else if(dp[x][y] == dp[x][y-1])
y--;
}
System.out.println(dp[firstInput.length()][secondInput.length()]);
System.out.print(sb.reverse().toString());
}
}
'algorithm' 카테고리의 다른 글
[JAVA] 백준 1932번 : 정수 삼각형 (0) | 2020.09.29 |
---|---|
[JAVA] 백준 2225번 : 합분해 (0) | 2020.09.23 |
[JAVA] 백준 2631번 : 줄세우기 (0) | 2020.09.14 |
[JAVA] 백준 3020번 : 개똥벌레 (0) | 2020.09.14 |
[JAVA] 백준 2667번 : 단지번호붙이기 (0) | 2020.09.10 |