[백준BOJ] 1120번 문자열.java

 

백준 저지에서 문자열을 자바를 통해 풀어 보았다. 

 

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

1120번: 문자열

1120번 문자열.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

1120번 문자열

문제

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.
두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

1. A의 앞에 아무 알파벳이나 추가한다.
2. A의 뒤에 아무 알파벳이나 추가한다.

이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

설명

문자열 A, B의 최대 길이가 50이라 완전탐색으로 풀어도 충분할 것 같아서 브루트포스로 풀었다.  

 

A의 앞 뒤에는 아무 알파벳을 추가할 수 있다. 즉 현재 A의 길이와 상관없이 앞뒤로 오는 문자열은 B와 같은 문자를 둘 수 있다. 결국 추가되는 문자는 신경쓰지 않고 현재 A와 B의 상태만 비교하면 된다.

 

B의 문자열 중 시작점을 정하여 시작점부터 A의 길이만큼만 A와 비교하여 다른 문자의 개수를 찾는다. 이 과정을 B의 문자열에서 가능한 모든 시작점에서 수행한다. 그렇게 찾은 A와 B의 차이들 중 가장 최솟값을 출력한다.

코드

//1120번 문자열.java
package week3;

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

public class 문자열_1120 {
	private static String A;
	private static String B;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		StringTokenizer st = new StringTokenizer(line," ");
		
		String A = st.nextToken();
		String B = st.nextToken();
		int answer = 50;
		for(int i=0;i<B.length()-A.length()+1;i++){
			int temp=0;
			for(int j=i;j<A.length()+i;j++) {
				if(B.charAt(j)!=A.charAt(j-i)) {
					temp++;
				}
			}
			answer = (answer>temp)? temp:answer;
		}
		System.out.println(answer);
	}
}