[Baekjoon]1120번 문자열 - Javascript

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의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

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

이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

예제 입력 1 복사

adaabc aababbc

예제 출력 1 복사

2

예제 입력 2 복사

hello xello

예제 출력 2 복사

1

 

문제풀이(1)

문자열 A를 B에 겹쳤을 때 다른곳의 최소값을 구하면된다.
A문자열의 길이 - B의 문자열의 길이만큼 반복순회하고,
B의 문자열을 한칸씩 뒤로 미루면서 다른곳을 count하여 가장 작은 값을 찾아낸다. -> 슬라이딩 윈도우 기법

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [A, B] = require("fs").readFileSync(filePath).toString().trim().split(" ");

let min = Infinity;

// A와 B의 차이만큼 반복한다.
for (let i = 0; i <= B.length - A.length; i++) {
  let diff = 0;
  // 한칸씩 뒤로 미루면서 가장 차이가 적은 것을 골라낸다.
  for (let j = 0; j < A.length; j++) {
    if (A[j] !== B[i + j]) {
      diff++;
    }
  }
  min = Math.min(min, diff);
}

console.log(min);