[백준] 1120 문자열 JAVA

혅·2024년 3월 24일

Java

1일1백준 -Java-

목록 보기

5/60

문제

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.

두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

A의 앞에 아무 알파벳이나 추가한다.
A의 뒤에 아무 알파벳이나 추가한다.
이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

예제 입력

koder topcoder

예제 출력

내가 했던 풀이 방법

indexOf를 이용하여 값이 0일 때, 문자열 뒤에 B.charAt(A.length)를 넣는다. -> 실패 (입력된 A가 항상 B에 들어있는 문자열이 아니고 -1을 반환할 때 방법을 찾을 수 없음)
추가로 붙은 알파벳은 항상 일치하므로, A를 B와 일치하는 부분과 덩어리를 찾고 그 index를 기준으로 앞 뒤에 붙임 -> 실패 (B와 length가 같아지면 알파벳을 추가하지 않으므로, A가 이동할 수 있는 범위가 한정적임)
A의 이동을 B의 시작부터 시작하여, 오른쪽으로 이동하면서 알파벳의 차이가 최소가 되는 값을 찾음. 즉, "CDE", "ABCDEFG"가 있을 때, "ABC", "BCD", "CDE" ... 순으로 A의 시작 index를 +1하면서 A와 B의 차이가 최소가 되는 값을 찾음. -> 성공

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");

        String A = input[0];
        String B = input[1];

        int min = B.length();
        int diff;
        for(int i=0; i<=B.length()-A.length(); i++) {
            diff = 0;
            for(int j=0; j<A.length(); j++) {
                if(A.charAt(j)!=B.charAt(j+i)) {
                    diff++;
                }
            }
            if(diff<min) {
                min = diff;
            }
        }

        System.out.print(min);

    }
}