[백준 1120] 문자열 with Node.js

문제 링크

www.acmicpc.net/problem/1120

1120번: 문자열

풀이

const [a, b] = require("fs").readFileSync("/dev/stdin").toString().trim().split(" ");
let min = a.length;
for (let i=0; i<=b.length-a.length; i++) {
    let curMin = 0;
    for (let j=i; j<i+a.length; j++) {
        if (a[j-i] !== b[j]) curMin++;
    }
    if (curMin < min) min = curMin;
}
console.log(min);

A와 B의 차이의 최솟값은 연산을 하기 전 상태에서 A를 B에 겹쳤을 때, 가장 적은 차이를 내는 경우가 있다면 그 차이가 최솟값이다. 왜냐 하면, 연산은 A의 나머지 부분을 모두 B와 같게끔 해야 최솟값이 나오기 때문에 연산을 하기 전 상태에서 이미 최솟값을 알 수 있다.

 

A를 adaabc, B를 aababbc라고 할 때, A를 B에 겹치는 두 가지 경우가 있다.

 

aababbc

adaabc

이렇게 겹치면 차이가 3이 된다. A의 나머지 부분은 뒤에 c를 넣으면 되니까 어차피 최솟값에는 변함이 없다.

 

aababbc

aadaabc

이렇게 겹치면 차이가 2가 된다.  A의 나머지 부분은 앞에 a를 넣으면 되니까 어차피 최솟값에는 변함이 없다.