[BOJ] 5582 공통 부분 문자열

공통 부분 문자열

풀이

• 두 문자열이 주어졌을 때, 공통으로 포함된 "부분문자열" 중 가장 긴 것을 찾는 문제.
• 3중 반복문 구현으로 풀었을 때 통과가 되긴 했다..
  
  이런 결과로 ^^.. 그래서 더 효율적인 코드로 구현해야겠다고 생각..
  일단 위 풀이를 적어보자면

  😃 아쉬운 풀이

  import java.util.*;
  import java.io.*;
  public class Main {
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          String str1 = br.readLine();
          String str2 =br.readLine();
          String minStr = (str1.length()<str2.length()?str1:str2);
          String maxStr = (str1.length()<str2.length()?str2:str1);
          int[] memo = new int[maxStr.length()];
          int answer = 0;
          for(int i=0;i<minStr.length();i++){
              for(int j=0;j<maxStr.length();j++){
                  if(minStr.charAt(i)==maxStr.charAt(j)){
                      int cnt = memo[j];
                      while(j+cnt<maxStr.length() && i+cnt<minStr.length()){
          			 if(minStr.substring(i,i+cnt+1).equals(maxStr.substring(j,j+cnt+1))){
                              cnt++;
                          }
                          else break;
                      }
                      if(cnt>memo[j]){
                          for(int k=j;k<j+cnt;k++){
                              memo[k] = cnt--;
                          }
                          answer = Math.max(answer,memo[j]);
                      }
                  }
              }
          }
          System.out.println(answer);
      }
  }

  1. 먼저 주어진 문자열 두개에서 짧은 문자열, 긴 문자열을 따져줬다. for문 돌릴 때 짧은 문자열 기준으로 돌리기 때문.
  2. 짧은 문자열의 i번째 문자에 대해 긴 문자열의 문자들과 하나씩 비교하는 2중 for문을 구현했다.
  3. 문자열이 같은 부분이 나왔다면, 그 뒷부분도 같은지 while문을 이용해서 확인한다.
  4. memo[j] 는, 긴 문자열의 j번째 문자에 대해서, 그 문자로 시작하는 공통 부분 문자열의 최대 길이를 저장하는 배열이다. 만약, 저장된 길이 보다 cnt 값이 커진 경우, 즉 더 긴 부분 문자열을 찾은 경우, 갱신해준다.

내 코드이지만 ... 설명하려 하니 엥 이거 왜이렇게 짰니? 싶었다. 좋은 코드가 아니라는 거겠지~...

• 더 나은 코드를 찾아봤다. dp 문제였던 것이다..

  🙆‍♀️ dp 코드

  import java.util.*;
  import java.io.*;
  public class Main {
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          String str1 = br.readLine();
          String str2 = br.readLine();
          int answer = 0;
          int[][] dp = new int[str1.length()+1][str2.length()+1];
          for(int i=1;i<=str1.length();i++){
              for(int j=1;j<=str2.length();j++)
              {
                  if(str1.charAt(i-1)==str2.charAt(j-1)){
                      dp[i][j] = dp[i-1][j-1]+1;
                      answer = Math.max(answer,dp[i][j]);
                  }
              }
          }
          System.out.println(answer);
      }
  }

  1. dp 배열을 이용하는데, dp[i][j]는 "해당 행,열까지의 문자만을 사용했을 때의 공통 부분 문자열의 갯수"이다.
     
     
     
     
  2. 그림에서 보면 , 동그라미 쳐져있는 3은 "ABR"과 "ECADADABR" 간의 공통 부분 문자열의 갯수이다.("ABR")
     근데 이것은, "AB"와 "ECADADABR"간의 공통 부분 문자열 갯수 2 에 +1을 한 값이다.
     즉, dp[i][j] = dp[i-1][[j-1]+1 로 갱신할 수 있다는 것이다.