TIL 백준 1120 문자열

해당 문제는 무작위 문자열에서 같은 문자의 개수가 가장 많은(가장 닮은 문자)를 찾아서 해당 경우의 수의 틀린문자 차이(최소차이)를 구해내는 문제이다.

 

문제 설명​

길이가 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의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.​

 

문제링크 : https://www.acmicpc.net/problem/1120

 

난 이 문제를 문자 크기 차이만큼 돌도록 만들어서 문자열이 들어갈 수 있는 경우의 수를 모두 체크하고 틀린문자카운트가 가장 작은 경우의 개수를 출력했다.

 

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

public class Main {

    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());

      String A = st.nextToken();
      String B = st.nextToken();
      Integer result;

      result = containsCharCnt(A,B);  //최솟값 구하는 함수에 문자열 2개 매개변수로 전달

      System.out.println(result);
    }
    private static Integer containsCharCnt(String a, String b){
      char[] arrayA = a.toCharArray();
      int cnt;
      int min = a.length(); //최솟값을 찾을 것이므로 최대로 나올 수 있는 값으로 초기화
      for(int i = 0;i<=b.length()-a.length();i++){  //a가 b에 들어갈 수 있는 경우의 수만큼 반복
        cnt = 0;
        int lastIndex =i+a.length();  //문자열을 자를 때 마지막 인덱스 값 초기화

        String temp = b.substring(i,lastIndex); //b문자열을 a크기만큼 한칸씩 옮기며 자르기

        char[] arrayTemp = temp.toCharArray();
        
        for(int j =0;j<arrayTemp.length;j++){
          if(arrayA[j] != arrayTemp[j]){  //문자마다 같은지 검사
            cnt++;
          }
        }
        min = Math.min(min,cnt);  //최소값 초기화
      }
      return min;
    }

}