[BOJ][JAVA] 1120 - 문자열

문제 출처 : https://www.acmicpc.net/problem/1120

1120번: 문자열

 

 

 

문제

 

 

설명

조금 어렵게 느껴질 수도 있는 문제인데, 차근차근히 원리를 생각해보면 생각보다 쉬운 문제입니다.

제 아이디어는 다음과 같습니다.

B와 같아질 때까지 A의 앞뒤로 아무 문자나 붙일 수 있기 때문에 A가 B의 위를 왼쪽부터 오른쪽으로 돌아다니며 서로 다른 알파벳의 차이가 최소인 위치를 찾습니다. 그 위치를 찾았다면, 그 차이만큼 B와 똑같이 되게 A에 알파벳을 앞뒤로 붙이면 되기 때문에, 그 차이가 바로 답이 됩니다. 

 

 

코드

import java.util.Scanner;

public class BOJ1120 {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		String A = sc.next();
		String B = sc.next();
		//문자열로 변환
		char[] newA = A.toCharArray();
		char[] newB = B.toCharArray();
		
		int min = 51;
		
		int iter_num = newB.length-newA.length+1; //넓게 본 반복 횟수
		int i = 0;//(넓게) 몇 번째 반복인지
		int j=0;//newB의 인덱스
		
		while(iter_num>0) {
			j=i; //newB의 인덱스를 다시 세팅
			int cnt=0;
			for(int k=0; k<newA.length; k++) {
				if(newA[k]!=newB[j])
					cnt++;
				j++;
			}
			if(cnt<min)
				min=cnt;
			i++;
			iter_num--;
		}
		
		System.out.println(min);
	}
	
}