연습장/백준(BOJ) 문제풀이
[백준 1120] 문자열 with Node.js
Tesseractjh
2021. 4. 26. 01:58
문제 링크
1120번: 문자열
길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의
www.acmicpc.net
풀이
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를 넣으면 되니까 어차피 최솟값에는 변함이 없다.