[백준 5582 / Gold5] 공통 부분 문자열 - Java(자바)/Swift(스위프트)

❓문제 설명

작성자 : 김민규
문제 링크 : https://www.acmicpc.net/problem/5582

• 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.
  어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.
  두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

❗입출력

[입력]
첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.
[출력]
첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.
[예시]

🎁 문제 풀이

• dp라는 2차월 테이블을 생성합니다.
  • [예시] s : ABA | t : ABAB
    
• 위의 테이블에서처럼 공통된 문자열의 길이를 저장합니다.
• dp테이블에 저장된 값 중에서 최댓값을 출력합니다.

🖥️ 코드

Java

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

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

        String s = sc.nextLine();
        String t = sc.nextLine();

        int[][] dp = new int[s.length()+1][t.length()+1];

        int max = 0;

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); j++) {
                if (s.charAt(i-1) == t.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        System.out.println(max);
    }
}

swift

import Foundation

let s = Array(readLine()!)
let t = Array(readLine()!)

var dp = Array(repeating: Array(repeating: 0, count: t.count + 1), count: s.count + 1)
var ans = 0

for i in 1...s.count {
    for j in 1...t.count {
        if s[i - 1] == t[j - 1] {
            dp[i][j] = dp[i - 1][j - 1] + 1
            ans = max(ans, dp[i][j])
        }
    }
}

print(ans)