백준 17218 비밀번호 만들기 (Java)

1. 문제 링크

2666번: 벽장문의 이동

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. dp 이차원 배열을 만들어 현재 위치까지의 최장길이를 저장한다.

2. 뒤에서부터 둘 중 하나를 다 읽을때까지 반복한다.

    2-1. 현재 두 인덱스에서의 값이 동일할 경우 결과 앞에 더하고 각 인덱스 값에 1을 뺀다.

    2-2. 같지 않은 경우에는 dp배열에서의 값이 작은 문자열 길이 인덱스 값에서 1을 뺀다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String one = br.readLine();
		String two = br.readLine();
		
		int len1 = one.length();
		int len2 = two.length();
		
		int[][] dp = new int[len1+1][len2+1];
		//같은 문자가 나오면 값 증가
		for(int i=0;i<len1;i++) {
			for(int j=0;j<len2;j++) {
				if(one.charAt(i) == two.charAt(j)) {
					dp[i+1][j+1] = dp[i][j]+1;
				}
				else {
					dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);
				}
			}
		}
		
		String result = "";
		
		//하나라도 끝까지 읽으면 끝
		while (len1!=0 && len2!=0) {
			if (one.charAt(len1-1) == two.charAt(len2-1)) {
				result = one.charAt(len1-1)+result;
				len1--;
				len2--;
			}
			else {
				//같지 않은 경우에는 같은 곳을 찾기 위해서 dp가 일치할 때까지 자리 이동
				if (dp[len1][len2-1]<dp[len1-1][len2]) {
					len1--;
				}else {
					len2--;
				}
			}
		}
		System.out.println(result);
		
	}
}