[백준-자바] 1120번 문자열 / 2022.05.09

 

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

1120번: 문자열

 

 

import java.util.Scanner;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String A = sc.next();
        String B = sc.next(); // 문자열 A와 B입력
        int cha = 0; // 문자 차이 개수
        int [] minSub = new int [B.length()-A.length()+1]; // 차이가 가장 적을 때를 구하기 위한 배열

        for(int i=0; i<=B.length()-A.length(); i++){ // B의 문자열을 0번 부터 A의 크기만큼 떼어서 보기
            cha = 0;
            String newB = B.substring(i, i+A.length()); // 자른 문자열을 새 문자열로 선언
            for(int j=0; j<A.length(); j++){ // 자른 문자열 newB와 A 문자열 비교
                if(newB.charAt(j) != A.charAt(j)) // 다른 문자열이 있다면
                    cha++; // cha += 1
            }
            minSub[i] = cha;
        }
        // 가장 적은 차를 구함
        Arrays.sort(minSub);
        System.out.println(minSub[0]);
    }
}

 

풀이 : 

A 가 abc 

B 가 topabcoder 라면, 

abc <-> top --> cha = 3

abc <-> opa  --> cha = 2

abc <-> pab --> cha = 1

abc <-> abc --> cha = 0

abc <-> bco --> cha = 1

abc <-> cod --> cha = 2

abc <-> ode --> cha = 3

abc <-> der --> cha = 3

 

따라서 가장 적은 차이는 0 

 

문제의 조건인 앞이나 뒤에 문자열을 추가하는 건 따로 생각하지 않아도 된다. (가장 적은 차를 구하고 나머지는 똑같은 알파벳을 붙이면 되기 때문에 )

위의 코드에선 substring을 사용하여 새로운 문자열을 만들고 비교했는데 for문에서 index값으로 접근해줘도 된다.