백준 1120 문자열 / C++

문제 : 2293

풀이 point

가장 일치하는 부분을 먼저 구한 후 앞 or 뒤에 값을 추가해서 최대로 일치하도록 만든다.(최대 일치 = 차이 최소)

풀이 방법

B의 가장 처음과 A의 가장 처음을 비교한다. 그 다음은 B의 두번째 부분과 A의 가장 처음을 비교한다. B의 길이와 A의 길이 차 만큼 모든 경우를 보았다면 가장 일치한 인덱스를 체크한다.

가장 일치한 인덱스에서 (B의 처음 인덱스 - 인덱스 위치) + (B의 마지막 인덱스 - 인덱스 위치)를 하면 차이가 최소로 된다.

코드

//백준 1120, 문자열

#include <iostream>

int main(){

    //adaabc
    //aababbcde

    std::string a, b;

    std::cin >> a >> b;

    auto lenA = a.length();
    auto lenB = b.length();

    if(lenA == lenB){
        int ans{0};
        for(int i{0}; i<lenA; ++i){
            if(a[i] != b[i]) ++ans;
        }
        std::cout << ans;
    }
    else{
        int min{100}; int idx;
        for(int i{0}; i<=lenB-lenA; ++i){
            int ans{0};
            for(int j{0}; j<lenA; ++j){
                if(a[j] != b[j+i]) ++ans;
            }
            min = std::min(min, ans);
        } 
        std::cout << min;
    }
    
    return 0;
}

2025-03-13T06:18:05.580Z