BOJ - 9252 ) LCS 2

개발자가될수있을까? 2020. 8. 25. 19:56

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

9252번: LCS 2

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

https://algorithmstudy-mju.tistory.com/161

BOJ - 9251 ) LCS

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를..

algorithmstudy-mju.tistory.com

LCS 1 에 이어서 LCS 2 는 LCS의 길이 뿐만아니라 그 LCS 가 뭔지 역추척하는 과정을 필요로 한다.

1 ) 좌, 좌상, 상 의 값이 같고 내가 그들보다 +1 크면 같아서 LCS길이가 증가한경우이다.

2 ) 아닌경우 좌, 좌상, 상 중 가장 큰값으로 이동한다.

이 두가지가 LCS의 길이가 0 인상태까지 반복하면 LCS를 거꾸로 뒤집은 문자열을 얻을 수 있다.


import java.io.BufferedReader;
import java.io.InputStreamReader;

public class LCS2 {

   public static void main(String[] args) throws Exception {
   
      BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
      String strA = br.readLine();
      String strB = br.readLine();
      int map[][] = new int[strA.length()+1][strB.length()+1];
      for(int i = 1 ; i < strA.length()+1 ; i++) {
         for(int j = 1 ; j < strB.length()+1 ; j++) {
            if(  strA.charAt(i-1) ==    strB.charAt(j-1)  ) {
               map[i][j] = map[i-1][j-1]+1;
            } else {
               map[i][j] = max(map[i-1][j], map[i][j-1]);
            }
         }
      }
      StringBuilder sb = new StringBuilder();
      sb.append(map[strA.length()][strB.length()] + "\n");
      
      int y = strA.length();
      int x = strB.length();
      String Answer ="";
      while(map[y][x] != 0) {
         if(map[y-1][x] == map[y-1][x-1] && map[y-1][x-1] == map[y][x-1] && map[y-1][x-1] < map[y][x]) {
            // 저장하고 
            Answer +=  strA.charAt(y-1);
            y--;x--;
         } else {
            // 큰쪽으로 이동, 가장 큰값의 y,x를 대입
            if(map[y-1][x] < map[y-1][x-1]) {
               if(map[y-1][x-1] < map[y][x-1]) {
                  x--;
               } else {
                  y--;x--;
               }
            } else {
               if(map[y-1][x] > map[y][x-1]) {
                  y--;
               } else {
                  x--;
               }
            }
         }
      }
      for(int i =  Answer.length()-1 ; i >=0 ; i--) {
         sb.append(Answer.charAt(i));
      }
      System.out.println(sb);
   
   }

   private static int max(int i, int j) {
      return i = i > j ? i : j ;
   }
}