백준 ] 1120번 - 문자열

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의 길이보다 작거나 같다.

이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

1. A의 앞에 아무 알파벳이나 추가한다.
2. A의 뒤에 아무 알파벳이나 추가한다.

여기서 우리가 알 수 있는 것은

 

A의 길이는 B보다 작거나 같고, A의 앞이나 뒤에 아무 알파벳이나 추가해서 길이를 같게 만들 수 있다.

그리고 A와 B의 차이를 최소로 만들어야 한다.

 

그러니까

A가 adaabc이고,

B가 aababbc라고 하자.

 

1) A : adaabc / B : aababb -> 차이 3

2) A : adaabc / B : ababbc -> 차이 2

 

따라서 최소값인 2가 출력된다.

 

따라서 A와 B의 길이 차만큼 for문을 돌면서

A와 B끼리 문자의 차이를 check하고, 최소 check 수를 출력하면 된다.

 

 

 처음 풀이

 

: 문제 이해가 안 가서 걍 내 맘대로 풀고 틀림 ㅎ

#include <iostream>
#include <string>
using namespace std;

int main() {
	string x = "adaabc", y = "aababbc";
	int answer = 0;
	
	cin >> x >> y;
	if(x.size() == y.size()){
		for(int i = 0; i < x.size(); i++){
			if(x[i] != y[i]) answer++;
		}
	}
	else{
		// A 사이즈만큼 ( A는 B보다 작으므로 )
		answer = y.size() - x.size();
		
		for(int i = 0; i < x.size(); i++){
			if(x[i] != y[i]) {
				answer++;
				break;
			}
		}
	}
	
	cout << answer;
	
	return 0;
}

 

 

 

🌱 정답코드

#include <iostream>
#include <string>
using namespace std;

int main() {
	string x = "", y = "";
	int answer = 50, temp = 0;
	
	cin >> x >> y;
	
	for(int i = 0; i <= y.size() - x.size(); i++){
		temp = 0;
		for(int j = 0; j < x.size(); j++){
			if(x[j] != y[i + j]) temp++;
		}
		if(answer > temp) answer = temp;
	}
	
	cout << answer;
	
	return 0;
}