[1120번] 문자열

문제 기출 : [https://www.acmicpc.net/problem/1120]

 

 

풀이 방법

[그리디알고리즘] 접근   A는 B보다 같거나 짧다는 것을 기억한다.   (B.length() - A.length() + 1)만큼 반복해가면서 같은 문자를 체크할 것이다. B를 i부터 (i + A.length())만큼 잘라서(이하 B`) 그 길이만큼 반복해가며 A의 각 문자와 자른 B`의 각 문자를 비교. 같으면 카운트한다.   카운트한 것 중에 가장 큰 값을 출력하면 문제 의도를 만족시킬 수 있다.

 

문제 풀이

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int answer = 0;

		try {
			StringTokenizer expression = new StringTokenizer(br.readLine(), " ");
			String A = expression.nextToken();
			String B = expression.nextToken();

			int max_same = 0;
			for (int i = 0; i < B.length() - A.length() + 1; i++) {
				String temp_B = B.substring(i, i + A.length());
				int same = 0;
				
				for (int j = 0; j < temp_B.length(); j++) {
					if (A.charAt(j) == temp_B.charAt(j)) {
						same++;
					}
				}
				
				if (same > max_same) {
					max_same = same;
				}
			}

			System.out.println(A.length() - max_same);
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}