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

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

 

문제

최근 들어 개인정보 유출에 대한 뉴스를 많이 본 수형이는 한 사이트의 비밀번호가 유출 되더라도 다른 사이트에서 똑같은 비밀번호로 접속할 수 없도록 사이트마다 비밀번호를 다르게 설정하기로 다짐했다. 많이 고민한 결과 수형이는 눈을 감고 키보드를 막 쳐서 나온 두 문자열에서 공통으로 존재하는 가장 긴 부분 문자열을 비밀번호로 하기로 하였다. 수형이가 눈을 감고 만든 두 문자열이 주어졌을 때 비밀번호를 만드는 프로그램을 만들어보자.

 

유형 : LCS

 

접근 방식

• LCS 문자열을 구하는 문제이다.
• LCS 최대 길이를 구하고 해당 배열을 역추적해서 LCS 문자열을 구할 수 있다.
• LCS 길이 구하기
  • dp[i][j]
    • a[i] = b[i] : dp[i-1][j-1] + 1 
    • a[i] != b[i] : max(dp[i-1][j], dp[i][j-1])
• LCS 문자열 구하기
  • a[i] = b[i]
    • i-1, j-1
  • dp[i][j] = dp[i-1][j]
    • i-1
  • dp[i][j] = dp[i][j-1]
    • j-1

코드

import java.util.*;
import java.io.*;

public class BOJ_17218_비밀번호_만들기 {

    static char[] a;
    static char[] b;

    static int aLen, bLen;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        a = br.readLine().toCharArray();
        b = br.readLine().toCharArray();

        aLen = a.length;
        bLen = b.length;

        int[][] dp = new int[aLen + 1][bLen + 1];

        int max = 0;

        for(int i = 1 ; i <= aLen ; i++) {
            for(int j = 1 ; j <= bLen ; j++) {
                char tmpA = a[i-1];
                char tmpB = b[j-1];

                if(tmpA == tmpB) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }

                max = Math.max(max,dp[i][j]);
            }
        }

        StringBuilder sb = new StringBuilder();

        int startA = aLen;
        int startB = bLen;

        while(startA > 0 && startB > 0) {
            if(a[startA - 1] == b[startB - 1]) {
                sb.append(a[startA - 1]);
                startA -= 1;
                startB -= 1;
            }else if(dp[startA][startB] == dp[startA - 1][startB]) {
                startA -= 1;
            }else {
                startB -= 1;
            }
        }

        System.out.println(sb.reverse());

        br.close();
    }

}