자바(백준) 1120 문자열

오답 노트 & 새로 알게 된 점

문제를 보면 A에다가 앞, 뒤로 a~z까지 일일이 한 개씩 삽입한 뒤,

비교하려면 코드가 더러워지고 엄청 복잡할 것 같아서 다른 방법을 생각했다.

 

그래서 B를 가지고 문제를 해결해보려했다.

 

B를 가지고 A의 길이가 될 떄까지 모든 경우의 수를 조사해보면 된다.

즉 A = abcde

B = aabcdefgf일 때,

(앞에서 뺀 갯수, 뒤에서 뺀 갯수)로 표현하면

(0,4) (1,3) (2,2) (3,1) (4,0)이 이다.

 

이 때 초기에 설정해야할 최댓값은 모든 문자가 다 다를 경우이다.

즉 A의 길이이다.

 

---

코드

 

package BruteForce_Search;
 
import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static String a, b;
    static int ans;
 
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        //최댓값은 모두 다 다를 때
        ans = a.length();
 
        for (int i = 0; i + a.length() <= b.length(); i++) {
            ans = Math.min(ans, compareTwoString(a, b.substring(i, i + a.length())));
        }
 
        System.out.println(ans);
    }
 
    static int compareTwoString(String a, String b) {
        int cnt = 0;
        for (int i = 0; i < a.length(); i++) {
            if(a.charAt(i) != b.charAt(i)) cnt++;
        }
        return cnt;
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        a = st.nextToken();
        b = st.nextToken();
 
    }
}