# BOJ01120 문자열
https://www.acmicpc.net/problem/1120 (opens new window)
길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] != Y[i]인 i의 개수이다.
두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.
- A의 앞에 아무 알파벳이나 추가한다.
- A의 뒤에 아무 알파벳이나 추가한다.
이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 값을 찾는다.
# 문제 해석
A문자열은 B문자열의 길이보다 작거나 같다. 해당 문장이 의미하는 바는 기존의 A에 아무거나 맞는 문자를 앞 혹은 뒤로 추가할 수 있기 때문에 항상 맞는다고 가정한다.
예제로 주어진 A는 adaabc, B는 aababbc이다.
A의 문자열 길이는 6이다. B의 문자열 길이는 7이다.
A와 B를 비교할 수 있는 경우의 수는 7 - 6 + 1로 2가 된다. 이것을 문자로 표현하면 아래와 같다.
adaabc*
aababbc
차이: 3
*adaabc
aababbc
차이: 2
_ *는 항상 같다고 가정한다. _
# getDifferenceCount
private static int getDifferenceCount(String string, String otherString) {
int count = 0;
for (int i = 0; i < string.length(); i++) {
if (string.charAt(i) != otherString.charAt(i)) {
count++;
}
}
return count;
}
두개의 문자열을 인자로 활용하여 두 문자열의 차이 개수를 반환하는 메서드이다.
# getMinDifferenceCount
private static int getMinDifferenceCount(String a, String b) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < b.length() - a.length() + 1; i++) {
int count = getDifferenceCount(a, b.substring(i, a.length() + i));
min = Math.min(min, count);
}
return min;
}
b 문자열을 a길이만큼 잘라서 더 작은 개수를 구한다.
# 제출 코드
아래는 최종 제출 코드이다.
public class BOJ1120 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String a = scanner.next();
String b = scanner.next();
System.out.println(getMinDifferenceCount(a, b));
}
private static int getMinDifferenceCount(String a, String b) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < b.length() - a.length() + 1; i++) {
int count = getDifferenceCount(a, b.substring(i, a.length() + i));
min = Math.min(min, count);
}
return min;
}
private static int getDifferenceCount(String string, String otherString) {
int count = 0;
for (int i = 0; i < string.length(); i++) {
if (string.charAt(i) != otherString.charAt(i)) {
count++;
}
}
return count;
}
}