[BOJ] 1120번 : 문자열 (브루트포스)

백준 1120번 : 문자열

🔗 문제 링크

https://www.acmicpc.net/problem/1120

1120번: 문자열

 

---

💬 문제

 문자열 과  완전탐색(브루트포스) 에 대한 이해가 있다면, 충분히 풀 수 있는 문제다.

 

1. 문자열 A와 B가 주어질 때, 두 문자열을 비교해 차이나는 문자 개수를 구해주는 문제이다.
   
   - 문자열 A의 길이는 문자열 B보다 작거나 같다
   
   
2. 문자열 길이가 작다면, A의 앞이나 뒤에 아무 알파벳을 추가한다고 나와있다.
   
   - 이 부분 때문에 문자를 추가해주는 코드를 짜는 경우도 있지만, 사실 필요없는 과정이다
   - 예를 들어, ab와 abc가 있을 때, 끝에 어떤 알파벳을 추가해 abO와 abc를 비교할 수 있다. 이때 차이가 최소화되려면 O에는 무조건 c가 들어가야하므로, 겹치지 않는 부분은 무조건 같다고 생각하고 겹치는 부분끼리만 비교해 차이가 가장 적은 경우를 찾아내면 된다
   
   
3. 겹치는 경우를 비교할 때, 차이나는 문자 개수도 어떻게 겹치느냐에 따라 달라질 수 있다.
   
   - 예를 들어, ab와 abc가 주어질때, 1~2번째 문자끼리 비교하면 ab와 ab를 비교하는 것이므로 차이 개수는 0개다
   - 그러나 2~3번째 문자끼리 비교한다면, ab와 bc를 비교하는 것이므로 차이 개수는 2개다
   
   
4. 차이나는 문자 개수 중 최소값을 출력해준다.
   
   

 

---

💡 입력값 받아오기

JavaScript로 풀 경우, 입력값(input)을 어떻게 받아와야 할 지가 중요하다.

이 문제에서는 1번째 줄에 비교할 문자열 A와 B가 공백을 기준으로 주어진다. 공백을 기준으로 잘라주고 변수 A와 B에 각각 할당해주면 된다.

 

 

입력값을 받아오는 것과 관련해 더 자세한 내용은 아래 링크를 참고 바란다.

https://valueengine.tistory.com/2

[BOJ] Node.js로 백준(BOJ) 푸는 법 및 VSCode 환경 세팅

 

728x90

 

---

💻 풀이

이 문제는 완전탐색(브루트포스) 방식으로 풀 수 있다.

🔑 풀이1 : 완전탐색 (브루트포스)

• A와 B의 길이가 서로 다를 수 있으므로, 길이 차이를 lenDiff에 할당해준다.
  
  - 문자열 A의 길이는 B보다 작거나 같다
  
  
• 길이가 차이나는 만큼 B의 위치를 옮겨 비교해준다.
  
  - ab와 abcd를 비교한다면, ab를 abcd 또는 abcd, abcd와 비교해줘야 하므로, A와 B의 길이 차이 내에서 B가 이동한만큼 B의 인덱스 값에 더해 비교해준다
  - 길이 차이가 2이므로, B의 인덱스는 0-1에서 2-3까지 이동할 수 있다
  - 각각을 비교할 때, 차이나는 문자의 개수를 배열 cnt에 넣어준다.
  
  
• cnt 중 최솟값을 출력해준다.
  
  

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ');
[A, B] = input;

console.log(solution(A, B));

function solution(A, B) {
  const lenDiff = B.length - A.length;  // A와 B의 길이 차이
  const cnt = [];   // 다른 경우 리스트

  for (let i=0; i <= lenDiff; i++) {  // 길이차이만큼 옮겨가면서 비교
    let diff = 0;

    for (let j=0; j < A.length; j++) {
      if (A[j] !== B[j+i]) {  // 다른 경우가 있다면
        diff++;
      }
    }
    cnt.push(diff);
  }
  return Math.min(...cnt);  // 다른 경우가 가장 작은 경우
}

 

시간은 다음과 같이 걸렸다.