[Java] 백준 9252번 LCS2

https://j3sung.tistory.com/936

[Java] 백준 9251번 LCS

LCS문제에서 문자열 출력이 추가 된 문제입니다.

최장 공통 부분 수열의 길이와 문자열을 출력해야합니다.

문자열의 경우 DP를 통해 만들어진 배열을 사용했습니다.
끝점에서 왼쪽과 위쪽으로 이동하면서 탐색합니다.
왼쪽과 위쪽 모두 숫자가 다른경우 바뀐것이므로 대각선으로 이동하면서 문자를 넣어줍니다.

넣어준 문자를 역순으로 변경해서 출력해주었습니다.

int y = a.length();
int x = b.length();
if(arr[y][x] > 0) {
  while(x >= 1 && y >= 1) {
    if(arr[y-1][x] == arr[y][x]) {
        --y;
    } else if (arr[y][x-1] == arr[y][x]) {
        --x;
    } else {
            --y;
            --x;
            ans += a.charAt(y);
    }
  }
}

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    String ans = "";
    
    String a = br.readLine();
    String b = br.readLine();
    int[][] arr = new int[a.length()+1][b.length()+1];
    
    for(int i=1; i<=a.length(); ++i) {
    	for(int j=1; j<=b.length(); ++j) {
    		arr[i][j] = Math.max(arr[i-1][j], arr[i][j-1]);
    		if(a.charAt(i-1) == b.charAt(j-1)) {
    			arr[i][j] = Math.max(arr[i][j], arr[i-1][j-1] + 1);
    		}
    	}
    }
    
    int y = a.length();
  	int x = b.length();
  	if(arr[y][x] > 0) {
      while(x >= 1 && y >= 1) {
      	if(arr[y-1][x] == arr[y][x]) {
      		--y;
      	} else if (arr[y][x-1] == arr[y][x]) {
      		--x;
      	} else {
    			--y;
    			--x;
    			ans += a.charAt(y);
      	}
      }
  	}
    
    bw.write(arr[a.length()][b.length()] + "\n");
    for(int i=ans.length()-1; i>=0; --i) {
    	bw.write(ans.charAt(i) + "");
    }
      
  	bw.close();
  }
}