백준 1120 문자열[Java]

알파벳을 앞뒤로 추가해주면서 알파벳의 다른 부분 없이 최소화시켜주는 것을 요구하는 문제이다.  

최초 구현을 앞뒤로 "*" 를 추가해주면서 숫자를 계산하는 재귀 함수를 구현했는데, 메모리 오버가 나는 것이다... ㅠㅠ

abc abcdefghijklmnopqrstuvwxyz 이런식으로 테스트 케이스를 정해 돌려보니 답을 산출하는데 꽤 많은 시간을 소비한다.

    static int sol(String s1, String s2) {
        if (s1.length() == s2.length()) {
            return calcualter(s1, s2);
        }
        return Math.min(sol("*" + s1, s2), sol(s1 + "*", s2));
    }

    static int calcualter(String s1, String s2) {
        int result = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) == '*')
                continue;
            if (s1.charAt(i) != s2.charAt(i)) {
                result++;
            }
        }
        return result;
    }

메서드 만 살펴보자면 이런식으로 구현을 진행했다. 

 

다른 아이디어가 필요했다. 주어지는 문자열을 가지고 앞에서부터 매칭 하면서 이동하는 방법으로 두 번째 문자열의 처음부터 끝까지 탐색하기로 결정

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

class Main {
    static String s1;
    static String s2;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] input = bf.readLine().split(" ");
        s1 = input[0];
        s2 = input[1];
        int n = sol(s1, s2);
        System.out.println(n);
    }

    static int sol(String s1, String s2) {
        int answer = Integer.MAX_VALUE;
        for (int i = 0; i < s2.length()-s1.length()+1; i++) {
            answer = Math.min(answer,calcualter(i));
            if(answer == 0) return answer;
        }
        return answer;
    }
    static int calcualter(int idx) {
        int result = 0;
        for (int i = idx; i < idx+s1.length(); i++) {
            if(s1.charAt(i-idx) != s2.charAt(i)){
                result++;
            }
        }
        return result;
    }
}

다를 거 없이 대신 계산을 해주는 과정에 인덱스를 넘겨주어 어디부터 계산할지 를 정해주었다.