[백준] 15482번 - 한글 LCS [Java][C++]

문제 링크

---

1. 문제 풀이

한글로만 이루어진 두 문자열의 LCS를 구하는 문제로 LCS 알고리즘을 활용하면 구할 수 있는 것은 똑같지만 언어별 한글 처리에 주의해서 구현해야 한다.

---

2. 코드

1. Bottom-Up dp [Java]

InputStreamReader 가 입력 스트림을 유니코드 문자로 디코딩(기본적으로 UTF-8)해줘서 Java에서 영어든 한글이든 동일한 로직으로 해결할 수 있다.

import java.io.*;

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

        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();
        int N = str1.length;
        int M = str2.length;

        int[][] dp = new int[1 + N][1 + M];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        System.out.println(dp[N][M]);
    }
}

2. Bottom-Up dp [C++]

UTF-8에서 가 부터 힣 까지 모든 한글 문자는 3바이트다. 따라서 LCS를 비교할 때 복잡한 디코딩을 짜지 않아도 3바이트 단위로 전부 일치하는지 비교하는 방식으로 한글 LCS를 처리할 수 있다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s1, s2;
    cin >> s1 >> s2;

    int n = s1.size();
    int m = s2.size();

    vector<vector<int>> dp(3 + n, vector<int>(3 + m));
    for (int i = 3; i <= n; i += 3) {
        for (int j = 3; j <= m; j += 3) {
            if (s1[i - 3] == s2[j - 3] && s1[i - 2] == s2[j - 2] && s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 3][j - 3] + 1;
            } else {
                dp[i][j] = max(dp[i - 3][j], dp[i][j - 3]);
            }
        }
    }

    cout << dp[n][m];
}

---

3. 풀이 정보

1. Bottom-Up dp [Java]

언어	시간	메모리	코드 길이
Java 11	120 ms	18344 KB	759 B

2. Bottom-Up dp [C++]

언어	시간	메모리	코드 길이
C++ 17	28 ms	37460 KB	618 B

---