[JAVA] 백준 #5582 공통 부분 문자열: 시간 초과 오답 기록 | 해결

---

백준 #5582 공통부분 문자열

5582번: 공통 부분 문자열

호기롭게 도전한 백준 골드 레벨 문제!! 어, 생각보다 풀만 한데? 하면서 풀었는데, 그럼 그렇지 결과는 '시간 초과'다😅

그래도 나름 열심히 풀었고, 테스트 코드까지 열심히 작성한 나의 자랑스러운 오답 코드를 공유해보고자 한다.

참고로 Dynamic Programming을 사용한 정답 코드도 바로 다음에 포스팅할 예정이다.

🔒 문제 설명

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 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 이하이다.

 

🖥️ 출력

첫째 줄에 두 문자열에 모두 포함된 부분 문자열 중 가장 긴 것의 길이를 출력한다.

 

---

🗝️나의 해결 방법

이 문제를 보자마자 바로 직전에 풀었던 SWEA의 '파리 퇴치' 문제가 떠올랐다. 해당 문제는 사중 For문을 사용해서 해결했는데 여기서도 비슷한 로직으로 '완전 탐색'법을 사용해서 풀면 되겠다고 생각했다. 그렇다. 알고리즘에 무지한 내가 자신 있는 것은 <완전 탐색> 알고리즘뿐이다...😅 (아 네 알고리즘 공부 할 거예요 아 진짜로요) 그래도 아래 코드는 나름 예제에 대해 정답도 잘 뱉어내는데, 다만 시간이 너무 오래 걸릴 뿐이다. 하하. 그래서 버리긴 아까운 나의 자랑스러운 오답 코드를 기록해보려고 한다!

 

 

🐣오답 기록

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

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

        ArrayList<Character> a_list = new ArrayList<>();
        ArrayList<Character> b_list = new ArrayList<>();

        a.chars().mapToObj(i -> (char)i).forEach(i->a_list.add(i));
        b.chars().mapToObj(i -> (char)i).forEach(i->b_list.add(i));

        int a_size = a_list.size();
        int b_size = a_list.size();
        int max = 0;

        for(int i = 0; i < a_size; i++){
            for(int j = 0; j < b_size; j++){

                // 공통 문자 하나라도 찾으면, 공통 문자열 길이 찾는 함수 실행
                if(a_list.get(i).equals(b_list.get(j))){

                    int tmpI = i;
                    int tmpJ = j;

                    int length = 0;
                    while(tmpI < a_size && tmpJ < b_size){
                        if(a_list.get(tmpI).equals(b_list.get(tmpJ))){
                            length++;
                            tmpI ++;
                            tmpJ ++;
                        }
                        else break;
                    }

                    if(length>max) max = length;
                }
            }
        }
        System.out.println(max);
    }
}

코드 리뷰를 해보자면, 아마 이중 for문 안에 while문을 또 구성하면서 시간 복잡도가 무지막지하게 커진 덕분에 시간 처리가 된 것 같다. 사실 테스트 코드 결과만 봐도 중복되는 결괏값이 정말 많았다. 오케이 이건 나의 무지다 인정

 

앞으로 더 열심히 공부해야겠어!

---

 

마지막으로 테스트용 코드는 아래와 같다. 위 코드에 콘솔 출력을 추가해서 오류 났을 때 결과를 직관적으로 확인할 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

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

        System.out.println("hi");
        ArrayList<Character> a_list = new ArrayList<>();
        ArrayList<Character> b_list = new ArrayList<>();

        a.chars().mapToObj(i -> (char)i).forEach(i->a_list.add(i));
        b.chars().mapToObj(i -> (char)i).forEach(i->b_list.add(i));

        int max = 0;

        for(int i = 0; i < a_list.size(); i++){
            for(int j = 0; j < b_list.size(); j++){

                // 공통 문자 하나라도 찾으면, 공통 문자열 길이 찾는 함수 실행
                if(a_list.get(i).equals(b_list.get(j))){
                    System.out.println("-----------------");
                    int tmpI = i;
                    int tmpJ = j;
                    ///////
                    System.out.println("HIT: "+a_list.get(tmpI));

                    int length = 0;
                    while(tmpI < a_list.size() && tmpJ < b_list.size()){
                        System.out.println("i = "+tmpI+" j = "+tmpJ);
                        //////////
                        if(a_list.get(tmpI).equals(b_list.get(tmpJ))){
                            length++;
                            tmpI ++;
                            tmpJ ++;
                        }
                        else break;
                    }
                    System.out.println("lenght: "+length);
                    if(length>max) max = length;
                }


            }
        }

        System.out.println(max);

    }
}

 

 

테스트용 코드를 사용하면 아래처럼 친절하게 출력을 해준다 

 

 

그럼 다음에 정답 코드와 함께 돌아오겠다.