코딩 테스트
[백준] 1958번 : LCS 3
한 면만 쓴 종이
2023. 7. 25. 09:27
LCS 문제들을 차례대로 풀고있는데
이 문제 완전 뒷통수 제대로 맞... 그냥 내가 못해서 그런거긴 한데
암튼 그래서 포스팅한다..
처음에는 물론 3차원 배열을 생각하기는 했다.
그런데 3차원을 .... 어떻게? 라는 생각에 에이~ 아니겠지~ 하고
첫 문자열 & 두번째 문자열 의 lcs 를 구해서 도출된 문자열과 세 번째 문자열의 LCS를 이용해서 최종 답을 도출하도록 구했다.
짜잔 ...~
package baekJoon.gold;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class B1958 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1 = br.readLine();
String str2 = br.readLine();
String str3 = br.readLine();
String lcsOfTwo = makeLcsStr(calculate(str1, str2), str1, str2);
System.out.println(lcsOfTwo);
int[][] dp = calculate(str3, lcsOfTwo);
System.out.println(dp[str3.length()][lcsOfTwo.length()]);
}
static int[][] calculate(String str1, String str2) {
int[][] dp = new int[str1.length() + 1][str2.length() + 1];
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;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp;
}
static String makeLcsStr(int[][] dp, String str1, String str2) {
int x = str1.length();
int y = str2.length();
StringBuilder sb = new StringBuilder();
while (x > 0 && y > 0) {
if (dp[x][y] == dp[x - 1][y]) {
x--;
} else if (dp[x][y] == dp[x][y - 1]) {
y--;
} else {
sb.append(str1.charAt(x - 1));
x--;
y--;
}
}
return sb.reverse().toString();
}
}
그런데 4퍼센트쯤 가서 실패를 하는거다...
마구잡이로 반례를 찾다보니
abcdefg
dcfogu
xdwfu
의 경우 2가 답인데 1로 나오는거다...!
뭔가 크게 잘못됐다는 생각을 하고 중간 LCS 문자열을 출력해봤더니
cfg였다..
그제서야 전 lcs문제에서 아무 문자나 도출하라고 했던게 생각나며... LCS 문자열이 여러개일 수 있다는 생각을 하게되었다..
흑흑
결론은 3차원 배열을 사용하자! 이다.
package baekJoon.gold;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class B1958 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1 = br.readLine();
String str2 = br.readLine();
String str3 = br.readLine();
System.out.println(calculate(str1, str2, str3));
}
static int calculate(String str1, String str2, String str3) {
int[][][] dp = new int[str1.length() + 1][str2.length() + 1][str3.length() + 1];
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)) {
for (int k = 1; k <= str3.length(); k++) {
if (str2.charAt(j - 1) == str3.charAt(k - 1)) {
dp[i][j][k] = dp[i - 1][j - 1][k -1] + 1;
} else {
dp[i][j][k] = Math.max(dp[i - 1][j][k], Math.max(dp[i][j - 1][k], dp[i][j][k - 1]));
}
}
} else {
for (int k = 1; k <= str3.length(); k++) {
dp[i][j][k] = Math.max(dp[i - 1][j][k], Math.max(dp[i][j - 1][k], dp[i][j][k - 1]));
}
}
}
}
return dp[str1.length()][str2.length()][str3.length()];
}
}
이렇게 했다.
코드가 지저분하다.
속도 향상을 위해 str1 과 str2가 다르면 str3은 검사하지 않고 str3만큼 같지 않는 처리를 해줬는데..
코드가 너저분.... ㅠ
뭐가 좋은 코드일까
str1.charAt(i - 1) == str2.charAt(j - 1) && str2.charAt(j - 1) == str3.charAt(k -1)
이랑 위 코드중에..
ㅎ그흑
아무튼 통과..!!