[백준] 1120번 문자열 JAVA (자바) 풀이

문제 1120 (문자열, 브루트포스)

길이가 N으로 같은 문자열 X와 Y

X와 Y의 차이 = X [i] ≠ Y [i]인 i의 개수 (예, X = ”jimin”, Y = ”minji” 이면, 차이 = 4)

 

짧은 문자열 앞 혹은 뒤에 아무 알파벳 추가 연산을 반복해 문자열 길이를 같게 만든다

이때, 문자열 길이가 같으면서, 차이를 최소로 하는 프로그램을 작성해라

 

 

 [입력]

 

 :  첫째 줄에 A, B 길이 ( 최대 50 / A 길이 ≤ B 길이 / 소문자 )

 

 

 

 [출력]

 :  최소의 차이 출력

 

 

 

 [참고]

 

 

규칙찾기

 

1. 문자열 길이 차이 구하기
   1. A문자열에 몇개의 알파벳을 더 붙여야 하는지 알기 위해서
      
      
2. 문자열 길이 차이 = A 문자열 길이 만큼 다 순회하고 남은 개수
   
   1. 예를 들어 A = abc, B = eabcd 라면
      처음엔 A의 개수만큼 순회하면서 문자가 같은지 검사한다
      문자열 길이 차이가 2 = 순회하면 남는 글자는 2개
      A의 [abc]와 B의 [eab]가 같은지 검사하고 나면 남는글자는 B에서 c,d 2개이다
      
      
3. B문자의 순회 영역을 옮기고 싶다면 최대 B - A 개의 칸이 이동 가능하다
   
   
4. 추가하는 것에 기준을 두지 말 것
   
   1. 어차피 원하는 어떠한 알파벳도 넣을 수 있다
   2. 그렇다면 이미 고정돼서 변경이 불가한 A의 문자열이 B문자열의 몇번째 인덱스부터와 가장 비슷한지 찾아야 한다
   3. 고정된 A 문자열을 갖고 B문자열 처음부터 검사해서 안 맞는 문자 개수를 세고 그 중 최소값을 출력해라

 

 

 [코드]

 

import java.util.*;
import java.io.*;
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();
        int result = Integer.MAX_VALUE;
        
        for(int i=0; i<=B.length()-A.length(); i++){
            int count = 0;
            for(int j=0; j<A.length(); j++){
                if(A.charAt(j)!=B.charAt(j+i)){
                    count ++;
                }
            }
            result = Math.min(count, result);
        }
        System.out.println(result);
    }
}

 

 

 [해설]
     

 :  StringTokenizer st = new StringTokenizer(br.readLine());  입력 끊어읽기
    String A = st.nextToken();  A문자
    String B = st.nextToken();  B문자
    int result = Integer.MAX_VALUE;  최솟값을 비교하므로 초기 비교대상 = 가장 큰 값 (A길이로 해도 괜찮다)
       

 :  for(int i=0; i<=B.length()-A.length(); i++){  B - A 길이 차이만큼 B문자열을 이동하며 체크
            int count = 0;
            for(int j=0; j<A.length(); j++){  A의 문자 길이 만큼 순회 (= 나랑 틀린 문자 찾기)
                if(A.charAt(j)!=B.charAt(j+i)){  A문자는 고정 B문자는 한칸씩 옆으로 이동하며 틀린 문자 체크
                    count ++;  
                }
            }
            result = Math.min(count, result);  순회할 때마다 체크했던 문자 개수 중에 최솟값을 구해라
    }
      

 :  System.out.println(result);  결과 출력
    
    

 [시간 복잡도]

 

for문을 처음에는 B - A만큼 돌다가 속해 있는 두번째 for문에서는 A만큼 다시 순회한다

AB - A² 라고 한다면 시간 복잡도는 O(A ² ) 이다

 

 

이제 풀어보러 갈께요 :)

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

 

https://www.acmicpc.net/problem/1120

 

1120번: 문자열