[BOJ / Node.js] 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

 

Solve

• 차이의 최소를 구해야 하기 때문에 알파벳을 추가하였을 때, 추가된 알파벳이 항상 일치하다고 가정하였습니다. (추가된 알파벳이 다른 경우는 차이의 최소값이 나올 수 없기 때문에)
• 길이가 긴 문자열 B를 기준으로 문자열 A를 슬라이딩 형태로 비교하며 문자가 다를 경우 count를 하여 최소값을 도출합니다.(아래는 예시)

koder topcoder의 경우

topcoder

koder

 

topcoder

 koder

 

topcoder

   koder

 

topcoder

     koder

 

Code

const [a, b] = require("fs").readFileSync("/dev/stdin").toString().trim().split(" ");

let answer = Infinity;


for(let i = 0 ; i <= b.length - a.length; i++) {
    let count = 0;
    for(let j = i; j < i + a.length; j++) {

        if(b[j] !== a[j-i]) count++;

    }
    answer = Math.min(count, answer);
}

console.log(answer);