❓ LCS
🏷️ 관련 주제 : Dynamic Programming String
'LCS문제는 다이나믹 프로그래밍을 이용해서 풀 수 있다'고 엊그제 공부했기 때문에 다이나믹 프로그래밍을 이용한 풀이 코드를 작성하려고 하였습니다.
그런데 어제 풀었던 LIS 문제와는 달리 문자열 2개가 주어질 때는 어떻게 해야할 지 바로 떠오르지 않았습니다.
엊그제 공부할 때, LCS 코드도 따라 썼었는데도 막상 혼자서 코드를 작성하려고 하니 잘 되지 않았습니다.
게다가 어제 저녁 비기너 문제 풀고 풀이까지 쓰고나니 시간이 너무 늦어서 제출을 한번밖에 못 해 보았습니다.
그래도 포기하기는 싫어서
'조금만 더 해보고 안되면 그 코드 보면서 다시 코드를 작성해 보아야겠다.'고 생각하고 다시 문제를 풀어보았습니다.
💦 나의 시도
전에 보았던 LCS 풀이 코드를 떠올리며 작성해 본 코드
두 문자열의 각 알파벳을 비교하여 int형 이차원 배열 cnt를 할당하며 문제를 해결해 보려하였습니다.
이차원 배열 cnt를 맨 뒤의 알파벳부터 반복문을 통해 비교하였습니다.
cnt에서 각 원소의 위치와 그 관계에 대해 생각해 볼 때,
현재 위치가 1이면 여기에 영향을 주는 값은 2, 3, 4 위치의 값들이라고 생각하였습니다.
따라서 그 값들 중, 최댓값을 1에 적용시키고
두 문자열의 i, j 인덱스 알파벳이 동일하면 1을 증가시켜 주었습니다.
그리고 최종적으로 cnt[0][0]의 값을 출력해 주었습니다.
import java.io.*;
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[][] cnt = new int[str1.length() + 1][str2.length() + 1];
for (int i = str1.length() - 1; i >= 0; i--) {
for (int j = str2.length() - 1; j >= 0; j--) {
cnt[i][j] = Math.max(cnt[i + 1][j], cnt[i][j + 1]);
if (str1.charAt(i) == str2.charAt(j)) {
cnt[i][j]++;
}
}
}
System.out.println(cnt[0][0]);
}
}
❌ 틀렸습니다.
여기서 2나 3의 값을 가져오면 1의 값은 반영이 안되어야 하는데
두 문자열의 i, j 인덱스 알파벳이 동일하면 값을 1 증가시켜주어 틀린 것 같습니다.
제가 이번에 알게된 Testcase AC(Beta)에 해당 코드를 입력해 보면 다음과 같은 반례가 나옵니다.
반례
입력1:
JBJAEG
BJGEIEEKGJCEDGED오답 출력: 7
정답 출력: 4
입력2:
GFJGDGCIDABEKJAAEJD
DECDECEIGK오답 출력: 6
정답 출력: 5
하지만 당시 풀이 작성할 때에는 이 부분을 잘 몰랐어서
일단 두 문자열의 알파벳이 일치하는지 체크하는 코드와 가장 긴 문자열을 체크하는 부분을 분리하여 코드를 작성해 보았었습니다.
알파벳 일치 체크와 문자열 길이 체크를 분리
import java.io.*;
import java.util.Arrays;
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[][] cnt = new int[str1.length()][str2.length()];
for (int i = str1.length() - 1; i >= 0; i--) {
for (int j = str2.length() - 1; j >= 0; j--) {
if (str1.charAt(i) == str2.charAt(j)) {
cnt[i][j] = 1;
}
}
}
for (int i = str1.length() - 1; i >= 1; i--) {
for (int j = str2.length() - 1; j >= 1; j--) {
if (str1.charAt(i) == str2.charAt(j)) {
cnt[i - 1][j - 1] += cnt[i][j];
} else {
cnt[i - 1][j - 1] += Math.max(cnt[i][j - 1], cnt[i - 1][j]);
}
}
}
System.out.println(cnt[0][0]);
}
}❌ 틀렸습니다.
하지만 역시 틀렸죠?😝
반례
입력1:
KIHCAC
BJCKKEEFE오답 출력: 2
정답 출력: 1
입력2:
JDGBHKJGDDBG
FAICHECBDEGKIGABDII오답 출력: 6
정답 출력: 5
다음은 배열에 문자열을 체크하는게 익숙하지 않아 저에게 익숙한 재귀함수로 문제를 풀어보았습니다.
재귀함수를 이용한 풀이
import java.io.*;
public class Main {
public static int[][] equals01;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1 = br.readLine();
String str2 = br.readLine();
equals01 = new int[str1.length()][str2.length()];
for (int i = str1.length() - 1; i >= 0; i--) {
for (int j = str2.length() - 1; j >= 0; j--) {
if (str1.charAt(i) == str2.charAt(j)) {
equals01[i][j] = 1;
}
}
}
System.out.println(lcs(0, 0, 0));
}
public static int lcs(int i, int j, int cnt) {
if (i == equals01.length || j == equals01[0].length) {
return cnt;
}
int cnt1 = 0;
if (equals01[i][j] == 1) {
cnt1 = lcs(i + 1, j + 1, cnt + 1);
}
int cnt2 = lcs(i, j + 1, cnt);
int cnt3 = lcs(i + 1, j, cnt);
int result = Math.max(cnt1, cnt2);
result = Math.max(result, cnt3);
return result;
}
}⏱️ 시간 초과
예상은 했지만 역시 재귀함수로 문제를 풀려고 하니 시간 초과가 나오는 군요.😣
반례
입력1:
EEHKDDCBBDABHFCDI
HFFHHBAEGEBKG오답 출력: 시간 초과 (TLE) (1.205s)
정답 출력: 4
입력2:
AECBFBDFKKCHAA
GBHEKDAFJDEGKFKHF오답 출력: 시간 초과 (TLE) (1.206s)
정답 출력: 6
입력3:
AEGBHHEEIFKGJGCA
AGKCHAABHJGAJJJ오답 출력: 시간 초과 (TLE) (1.219s)
정답 출력: 7
계속 고민을 하다보니 점차 코드를 어떻게 써야할 지 보이는 것 같았습니다.
그래서 전에 봤던 LCS 풀이 코드를 생각하지 않고 두 문자열의 알파벳을 앞쪽부터 체크하는 형식으로 최장 길이 문자열을 구해보았습니다.
이차원 배열을 이용한 풀이
import java.io.*;
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 row = str1.length();
int col = str2.length();
int[][] cnt = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (str1.charAt(i) == str2.charAt(j)) {
cnt[i][j] = 1;
}
}
}
for (int i = 1; i < row; i++) {
cnt[i][0] = Math.max(cnt[i - 1][0], cnt[i][0]);
}
for (int i = 1; i < col; i++) {
cnt[0][i] = Math.max(cnt[0][i - 1], cnt[0][i]);
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
int result = Math.max(cnt[i - 1][j], cnt[i][j - 1]);
result = Math.max(result, cnt[i - 1][j - 1] + cnt[i][j]);
cnt[i][j] = result;
}
}
System.out.println(cnt[row - 1][col - 1]);
}
}두 문자열에 대한 각 인덱스의 알파벳 일치 여부(일치:1, 불일치: 0)를 이차원 int 배열 int[][] cnt에 할당해 주는 부분은 이전과 동일합니다.
다만, str1.length(), str2.length()를 계속 반복해 사용해서 row, col이라는 int형 변수에 할당해 준 뒤 사용하였습니다.
두 문자열의 인덱스 i, j의 알파벳을 비교할 때 다음 탐색할 인덱스를 알아봅시다.
- 두 알파벳이 동일한 경우, 다음 탐색할 인덱스는
i + 1,j + 1이 됩니다.
(이는(A, A)다음으로(C, P)를 탐색하는 것과 동일합니다.)
- 두 알파벳이 다른 경우, 다음 탐색할 인덱스는 (
i,j + 1) 또는 (i + 1,j)가 됩니다.
(이는(C, P)다음으로(c, c)또는(C, P)다음으로(A, P)를 탐색하는 것과 동일합니다.)
즉, 가장 긴 문자열 길이를 구하는 과정에서 cnt에 값을 할당할 때
1의 값을 가져오는 경우는1에서 비교한 두 알파벳이 일치했을 경우이므로4에는 (1+4)가 할당되어야 하고2나3의 값을 가져오는 경우는2나3의 숫자가 불일치 했을 경우이므로4에 해당 값이 덮어씌우게 되는 것입니다.
따라서 4의 위치에는 2, 3, (1 + 4) 중 최댓값이 할당되어야 합니다.
최종적으로 cnt의 가장 마지막 행, 가장 마지막 열의 원소를 출력합니다.
📑제출 기록 및 오답 원인
💯 해결 방법
import java.io.*;
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 row = str1.length();
int col = str2.length();
int[][] cnt = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (str1.charAt(i) == str2.charAt(j)) {
cnt[i][j] = 1;
}
}
}
for (int i = 1; i < row; i++) {
cnt[i][0] = Math.max(cnt[i - 1][0], cnt[i][0]);
}
for (int i = 1; i < col; i++) {
cnt[0][i] = Math.max(cnt[0][i - 1], cnt[0][i]);
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
int result = Math.max(cnt[i - 1][j], cnt[i][j - 1]);
result = Math.max(result, cnt[i - 1][j - 1] + cnt[i][j]);
cnt[i][j] = result;
}
}
System.out.println(cnt[row - 1][col - 1]);
}
}
