17218번: 비밀번호 만들기

문제 출처 : https://www.acmicpc.net/problem/17218

 

언어 : Kotlin

 

문제 설명 :

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

 

입력 :

첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는 최대 40자이다. 빈 문자열은 주어지지 않는다. 가장 긴 부분 문자열은 반드시 하나만 존재한다.

 

출력 :

첫 번째 줄에 입력으로 주어진 두 문자열로 만든 비밀번호를 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 256MB

 

입출력 예 :

입력	출력
AUTABBEHNSA BCUAMEFKAJNA	UAENA
SETAPPLE  EATMANY	ETA

 

풀이 : 

LCS 문자열을 찾는 문제.

dp[i][j] = "문자열 A의 0 ~ i - 1부터 문자열 B의 0 ~ y - 1중 가장 긴 부분 문자열의 길이"를 저장.

 

만약 A의 i번째 문자와 B의 j번째 문자가 같다면 직전까지 구한 긴 부분 문자열의 길이에 +1을 해준다.

같지 않다면, dp[i][j + 1]와 dp[i + 1][j] 중 큰 값을 넣어준다.

dp 배열을 전부 채운 뒤, LCS를 찾아내 출력한다.

 

LCS는 이전에 구한 dp배열에서 가장 긴 부분 문자열의 길이가 달라지는 구간을 찾아내 해당 구간의 문자를 출력하는 것을 반복하여 구할 수 있다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val arr = Array(2) { readLine() }
    val dp = Array(arr[0].length + 1) { IntArray(arr[1].length + 1) }
    
    for (i in 0 until arr[0].length) {
        for (j in 0 until arr[1].length) {
            if (arr[0][i] == arr[1][j]) dp[i + 1][j + 1] = dp[i][j] + 1
            else dp[i + 1][j + 1] = maxOf(dp[i][j + 1], dp[i + 1][j])
        }
    }

    val sb = StringBuilder()
    val index = IntArray(2) { 0 }.also {
        it[0] = arr[0].length
        it[1] = arr[1].length
    }

    with(index) {
        var i = this[0]
        var j = this[1]

        while (dp[i][j] != 0) {
            if (dp[i][j] == dp[i - 1][j]) i -= 1
            else if (dp[i][j] == dp[i][j - 1]) j -= 1
            else {
                sb.append(arr[0][i - 1])
                i -= 1
                j -= 1
            }
        }
    }

    bw.write(sb.reversed().toString())
    bw.flush()
    bw.close()
}