[ 백준 / BOJ 1958 ] LCS 3

[ 백준 / BOJ 1958 ] LCS 3

https://www.acmicpc.net/problem/1958

문제

문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.

이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.

입력

첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다.

출력

첫 줄에 첫 번째 문자열과 두 번째 문자열과 세 번째 문자열의 LCS의 길이를 출력한다.

풀이

처음에는 문자열 일치하는 최대 substring 의 길이를 구하는 것으로 착각해서 틀렷다.....

substring 이 아니라, subsequence 로 연속되지 않아도 된다‼️

그래서 Dynamic Programming 으로 풀었다.

DP[i][j][k] 는 1번째 문자열의 charAt(i) , 2번째 문자열의 charAt(j), 3번째 문자열의 charAt(k) 까지 일치한 문자의 갯수이다.

charAt(i) == charAt(j) == charAt(k) 이면,

DP[i][j][k] = DP[i-1][j-1][k-1] + 1 이고

하나라도 같지 않으면,

DP[i][j][k] = max( DP[i-1][j][k], DP[i][j-1][k], DP[i][j][k-1] ) 이다.

코드

틀린 코드

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] str = new String[3]; for(int i = 0 ; i < 3; i++){ str[i] = br.readLine(); } Arrays.sort(str, new Comparator(){ @Override public int compare(String o1, String o2) { return o1.length() - o2.length(); } }); int minLen = str[0].length(); int answer = 0; boolean flag = false; for(int i = minLen ; i >= 0 ; i--){ for(int j = 0; j < minLen; j++){ String s; if(i + j > str[0].length()) s = str[0].substring(j, str[0].length()); else s = str[0].substring(j, j+i); if(str[1].contains(s) && str[2].contains(s)){ answer = i; flag = true; break; } } if(flag) break; } System.out.println(answer); } }

맞은 코드

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; public class Main_BOJ_1958_LCS3 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] str = new String[3]; int[] len = new int[3]; for(int i = 0 ; i < 3; i++){ str[i] = br.readLine(); len[i] = str[i].length(); } int[][][] DP = new int[len[0]+1][len[1]+1][len[2]+1]; for(int i = 1 ; i <= len[0]; i++){ for(int j = 1 ; j <= len[1] ; j++){ for(int k = 1 ; k <= len[2] ; k++){ if(str[0].charAt(i-1) == str[1].charAt(j-1) && str[1].charAt(j-1) == str[2].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])); } } } } System.out.println(DP[len[0]][len[1]][len[2]]); } }

from http://hyeyun.tistory.com/12 by ccl(A) rewrite - 2021-09-15 21:27:01