[백준] 1120번: 문자열(그리디)

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

코드

import java.util.Scanner;

public class Main {
	public static String A;
	public static String B;
	public static int diffCount;	// 문자열 A, B 차이 

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		A = scan.next();
		B = scan.next();
		int result = A.length();	// A가 B보다 짧으므로, A의 길이만큼 지정
		
		for(int i=0; i<=B.length() - A.length(); i++) {
			diffCount = 0;
			for(int j=0; j<A.length(); j++) {
				if(A.charAt(j) != B.charAt(i+j)) {	// A는 0, 1, 2 고정이지만 B는 한칸씩 밀어짐
					diffCount ++;
				}
			}
			result = Math.min(result, diffCount);	// 최솟값
		}
		
		System.out.println(result);
		scan.close();
	}
}

 

풀이

조금 단순하게 생각해보니 풀 수 있었다.

입력받은 문자열 A, B의 예를 몇가지 들어보면 ...(길이: A <= B)

A = "aaa"

B = "abbc"

일때 차이는 2이다.

 

A = "aaa"

B = "bbccb"

일때 차이는 3이다.

 

A = "abca"

B = "bccdbca"

일때 차이는 1이다.

 

A = "aba"

B = "bdbbadb"

일때...

i=0 -> aba, bdb -> 2

i=1 -> aba, dbb -> 2

i=2 -> aba, bba -> 1

...

 

즉 B의 길이만큼 A 문자열을 오른쪽으로 한칸씩 이동하면서 A와 B의 부분 문자열을 비교하고,

비교한 값이 최솟값인걸 찾으면 된다.

 

동일한문제

위 문제는 이 문제와 동일한 로직으로 해결한 문제다 !