백준 9252번
https://www.acmicpc.net/problem/9252

문제

---

생각하기

---

• LCS의 기초를 다질 수 있는 문제이다.
  • TopDown(재귀) , BottomUp(반복문) 2가지 방식 모두로 구현했다.
  • 의문점 : 재귀로 구현한 코드는 메모리초과가 발생하지 않는데, 똑같은 코드를 반복문으로 고칠경우 메모리 초과가 발생함

동작

결과

코드

---

Kotlin

재귀

import java.io.*

// input
private lateinit var br: BufferedReader

// variables
private var s1 = ""
private var s2 = ""
private var N = 0
private var M = 0

private lateinit var memo: Array<Array<Memo>>

private data class Memo(var cnt: Int = -1, var str: String = "")

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

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    val temp = LCS(N, M)
    if (temp.cnt == 0) {
        sb.append(0)
    } else {
        sb.append(temp.cnt).append('\n').append(temp.str)
    }

    return sb.toString()
} // End of solve()

private fun LCS(n: Int, m: Int): Memo {
    if (n == 0 || m == 0) return Memo(0, "")

    if (memo[n][m].cnt != -1) return memo[n][m]

    if (s1[n - 1] == s2[m - 1]) {
        // 같을 때
        val temp = LCS(n - 1, m - 1)
        memo[n][m].cnt = temp.cnt + 1
        memo[n][m].str += temp.str + s1[n - 1]
    } else {
        // 다를 때
        val temp1 = LCS(n - 1, m)
        val temp2 = LCS(n, m - 1)

        if (temp1.cnt > temp2.cnt) {
            memo[n][m].cnt = temp1.cnt
            memo[n][m].str = temp1.str
        } else {
            memo[n][m].cnt = temp2.cnt
            memo[n][m].str = temp2.str
        }
    }

    return memo[n][m]
} // End of LCS


private fun input() {
    s1 = br.readLine()
    s2 = br.readLine()

    N = s1.length
    M = s2.length

    memo = Array(N + 1) { Array(M + 1) { Memo() } }
} // End of input()

반복문

import java.io.*

// input
private lateinit var br: BufferedReader

// variables
private var s1 = ""
private var s2 = ""
private var N = 0
private var M = 0

private lateinit var memo: Array<IntArray>

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

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    LCS(N, M)

    if (memo[N][M] == 0) {
        sb.append(0)
    } else {
        sb.append(memo[N][M]).append('\n').append(makeStr())
    }

    return sb.toString()
} // End of solve()

private fun makeStr(): String {
    var n = N
    var m = M
    var idx = memo[N][M] - 1
    val ret = StringBuilder()

    while (idx >= 0) {
        when {
            memo[n][m] == memo[n - 1][m] -> {
                n--
            }

            memo[n][m] == memo[n][m - 1] -> {
                m--
            }

            else -> {
                // if(memo[n][m] == memo[n - 1][m - 1])
                n--
                m--
                ret.append(s1[n])
                idx--
            }
        }
    }

    ret.reverse()
    return ret.toString()
} // End of makeStr

private fun LCS(n: Int, m: Int): Int {
    if (n == 0 || m == 0) return 0

    if (memo[n][m] != -1) return memo[n][m]

    if (s1[n - 1] == s2[m - 1]) {
        memo[n][m] = LCS(n - 1, m - 1) + 1
    } else {
        // 다를 때
        memo[n][m] = LCS(n - 1, m).coerceAtLeast(LCS(n, m - 1))
    }

    return memo[n][m]
} // End of LCS()

private fun input() {
    s1 = br.readLine()
    s2 = br.readLine()

    N = s1.length
    M = s2.length

    memo = Array(N + 1) { IntArray(M + 1) { -1 } }
} // End of input()