Algorithm/ACM-ICPC
[ID: 1120] 문자열
마산와사비
2020. 1. 6. 16:40
1120번: 문자열
길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다. A의 앞에 아무 알파벳이나 추가한다. A의 뒤에 아무 알파벳이나 추가한다. 이때, A와 B의 길이가 같으
www.acmicpc.net
- 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
String a = st.nextToken();
String b = st.nextToken();
System.out.println(getMinDiff(a, b));
}
public static int getMinDiff(String a, String b) {
if (a.equals(b)) {
return 0;
}
char[] aArr = a.toCharArray();
char[] bArr = b.toCharArray();
int ret = 100000;
for (int i = 0; i <= b.length() - a.length(); i++) {
int min = 0;
for (int j = i; j < i + a.length(); j++) {
if (bArr[j] != aArr[j - i]) {
min++;
}
}
if (min < ret) {
ret = min;
}
}
return ret;
}
}
- NOTE
- 작은 문자열을 큰 문자안에서 비교하면서 다른 문자열의 수가 최소가 되는 값을 구하면 된다.
- 예
- adaabc aababbc를 인덱스 0부터 비교하면 다른 문자열은 dac 총 3개
- 인덱스 1부터 비교하면 다른 문자열은 da 2개
- 따라서 최소값은 2이다.
- 예
- 추가하는 문자열의 경우 무조건 큰 문자열과 똑같은 값으로 추가할 것이기 때문에 추가하는 값에 대해서 고려할 필요는 없다.
- 작은 문자열을 큰 문자안에서 비교하면서 다른 문자열의 수가 최소가 되는 값을 구하면 된다.