백준 1120 - 문자열

https://www.acmicpc.net/problem/1120

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의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

(A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.)

 

 

문제풀이

---

완탐과 같이 진행한다. 먼저 길이가 같은 경우는 그냥 대소 비교가 가능하지만 다른경우를 고려해야 한다. 

keypoint: 완탐과 같은 방식으로 하나씩 이동해 나가면서 차이가 최소기되는 값을 구하면 된다.

(차이가 나는 부분은 같은 문자로 채울수 있기 때문이다.)

 

 

코드

---

#include<iostream>
#include <cstring>
#include<algorithm>
#include <cmath>
using namespace std;

int main(){
    string str1,str2;
    cin>>str1>>str2;
    int ans=0,temp=0,mini=9876;
    int limit= abs(int(str1.size())-int(str2.size()));
    
    //str1, str2 둘중의 길이가 작은 문자열을 찾기 위한 장치
    if(str1.size()>str2.size()) temp=1;
    else if(str1.size()<str2.size())temp=0;

	//차이나는 만큼 오른쪽으로 이동하면서 차이의 최소값을 찾아나간다.
    for(int i=0;i<=limit;i++){
        ans=0;
        for(int j=0;j<min(str1.size(),str2.size());j++){
            if(temp==1) str1[i+j]!=str2[j] ? ans+=1:ans+=0;     
            else if(temp==0) str2[i+j]!=str1[j] ? ans+=1:ans+=0; 
        }
        mini=min(ans,mini);
    }
    cout<<mini<<"\n";
    return 0;
}

 

 

funny algorithm :0 ~