[골드5] 9251. LCS (Java)

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

9251번: LCS

LCS규칙.. 하하.. 시간 너무 뺏겼습니다 ㅠㅠ

---

※  문제를 요약하면 아래와 같습니다.

▶ 두 단어가 주어졌을 때 (대문자 알파벳으로 구성되있는)  모두의 부분 수열이 되는 수열 중 가장 긴 수열의 길이를 반환

ex) AABBAA, AABBCDEGHA=>  LCS : AABBA

▶ 입력은 한 줄에 한 단어씩, 2단어가 입력

▶ 출력은 두 단어 중 가장 긴 부분 수열의 길이를 출력. 

ex) ACAYKP, CAPCAK -> LCS : ACAK -> 4개

◈ Input

ACAYKP
CAPCAK

◈ Output

4

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 여러가지 부분 수열(문자열)이 당연히 발생, 문자 하나씩 뿐만 아니라 문자열까지 포함하여 탐색 필요 

EX) AABBAA / ACCCDEFCSEBAA -> LCS : ABAA

▶ LCS 탐색 알고리즘 중 가장 긴 부분 수열 탐색 규칙 적용 

    : 두 단어의 문자를 하나씩 붙여가며 모든 경우의 수를 탐색.

      ex) ACAYKP, CAPCAK -> (A, C), (A, CA) , (A, CAP)....(AC,C), (ACA,C).....(ACAYKP, CAPCAK)

    : 탐색 과정을 표로 표현

  : 각각의 행과 열에 부분 수열 (겹치는 문자열)의 길이를 나열 하면

▶ 표에서 파란 부분이 색칠되 있는 곳은 행과 열의 단어가 일치

▶ 규칙 1 - i행과 j열의 단어가 일치할 경우, (i,j) = (i-1, j-1) 값의 +1

              (i-1, j-1)이 0보다 작을 경우는 0+1

▶ 규칙 2 - i행과 j열의 단어가 일치하지 않을 경우, (i,j) = (i-1,j) 와 (i, j-1)과 비교하여 높은 값 적용

 

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

public class Main{

	public static void main(String[] args) throws IOException  {
	    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	    
	    String strFirstWord = bf.readLine();
	    String strSecondWord = bf.readLine();
	    
	    int[][] arrTemp = new int[strSecondWord.length()][strFirstWord.length()];
	    int nMax = 0; 
	    
	    int nSearchi = 0;
	    int nSearchj = 0;
	    
	    for(int i = 0; i < strSecondWord.length(); i++) {
	        for(int j = 0; j < strFirstWord.length(); j++) {
	            nSearchi = i-1;
	            nSearchj = j-1;
	        	
	            // LCS-알고리즘 왼쪽과 위의 인덱스를 비교
	            if(strFirstWord.charAt(j) != strSecondWord.charAt(i)) {
	                // (i-1, j) 좌표와 비교
	            	if(nSearchi >= 0)
	                	arrTemp[i][j] = arrTemp[nSearchi][j] > arrTemp[i][j] ? arrTemp[nSearchi][j] : arrTemp[i][j]; 
	                // (i, j-1) 좌표와 비교
	                if(nSearchj >= 0)
	                    	arrTemp[i][j] = arrTemp[i][j] > arrTemp[i][nSearchj] ? arrTemp[i][j] : arrTemp[i][nSearchj];
	            } else if(strFirstWord.charAt(j) == strSecondWord.charAt(i)) {
	            	// (i-1),(j-1) 데이터 갖고와서 +1
	            	if(nSearchi >= 0 && nSearchj >= 0) {
	            		arrTemp[i][j] = arrTemp[nSearchi][nSearchj] + 1;
	            	} else
	            		arrTemp[i][j]++;
	            }
	            
	            if(nMax < arrTemp[i][j])
	                nMax = arrTemp[i][j];
	        }
	    }
	    System.out.println(nMax);
	}
}

 

LCS가 어떤 알고리즘 인지 알고 풀이를 진행했으면 시간이 덜 소요됬을 것 같은데, 혼자 끄적끄적 + SSAFY 동기의 힌트를 받으면서 증명 하다 보니 시간이 너무 오래걸렸네요.. CS도, 개인 프로젝트도 해야되는데 큰일,,,

읽어주셔서 감사합니다!

Good Luck! (피드백 고맙습니다)