[백준/c++] 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가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

구현해야 할 조건

일단 A,B의 길이가 최대 50이고, A의 길이는 항상 B보다 작다. 또한, A의 앞 또는 뒤에 아무 알파벳이지만 일단 맞는 알파벳을 넣는다는 가정하에 문제를 해결하자.

본인은 A 문자를 한칸씩 이동하면서 그 안에 A[i], B[i]의 문자가 다른것을 파악한것과, 무식하게 앞에 2 뒤에 1 앞 1 뒤 2 이런식으로 푸는것 두개를 준비해봤다. 코드상 한칸씩 이동하면서 문자가 다른 것을 파악하는 게 이쁘지만, 무식하게 푸는것도 방법이라면 방법이기에 두개를 올려봅니다!

code(무식하게 풀기)

#include<iostream>
#include<string>

using namespace std;

int ans = 0;
string A,B;
int minValue = 987654321;

int solve(int d){
	
	int front = d;
	int back = 0;
	
	while(1){
		
		if(front == -1)
			break;
					
		string str = "";
		for(int i = 0; i < front; i++)
			str += '*';
			
		string str2 = "";
		for(int i = 0; i < back; i++)
			str2 += '*';
			
		str += A;		
		str += str2;
		int cnt = 0;
		for(int i = 0; i < B.length(); i++){
			if(str[i] == '*') continue;
			if(str[i] != B[i]) cnt++;	
		}
		
		
		minValue = min(minValue, cnt);
		
		front--; back++;
	} 
	
	return minValue;
}

int main(){
	
	cin >> A >> B;
	
	if(A.length() == B.length()){
		
		for(int i = 0; i < A.length(); i++){
			if(A[i] != B[i])
				ans++;
		}
		
		cout << ans;
		
	}
	else{
		
		int diff = B.length() - A.length();
		cout << solve(diff);
		
	}
	
	return 0;
}

 

code(생각 조금 해서 풀기)

#include<iostream>

using namespace std;

int ans = 0;
string A,B;
int minValue = 987654321;

int solve(int d){
	
	for(int i = 0; i < d+1; i++){
		
		int cnt = 0;
		
		for(int j = 0; j < A.length(); j++){
			
			if(A[j] != B[i+j]){
				cnt++;
			}
		}
		
		minValue = min(cnt,minValue);
	}
	
	return minValue;
}

int main(){
	
	cin >> A >> B;
	
	if(A.length() == B.length()){
		
		for(int i = 0; i < A.length(); i++){
			if(A[i] != B[i])
				ans++;
		}
		
		cout << ans;
		
	}
	else{
		
		int diff = B.length() - A.length();
		cout << solve(diff);
		
	}
	
	return 0;
}