[기초 알고리즘] 가장 짧은 문자거리 - 자바스크립트

문제

한 개의 문자열 s와 문자 t가 주어지면 문자열 s의 각 문자가 문자 t와 떨어진 최소거리를 출력하는 프로그램을 작성하라.
문자열 s와 문자 t는 소문자로만 주어지며, 문자열의 길이는 100을 넘지 않는다.

입력 예제

teachermode, e

출력 예제

1 0 1 2 1 0 1 2 2 1 0

---

첫 풀이

1. 우선 거리를 구해야 한다.
   • e의 인덱스가 담긴 배열을 우선 구해보자.
   • 문자열 s를 순회하면서, s의 각 인덱스를 가지고 e의 인덱스가 담긴 배열의 요소 중에서 어떤 것과 가장 차이가 적은지를 구하자.

function solution(s, t) {
  let answer = "";
  let index = 0;
  const indexE = [];

  while (true) {
    let findIndex = s.indexOf("e", index);
    if (findIndex === -1) break;
    index = findIndex + 1;
    indexE.push(findIndex);
  }
  for (let i = 0; i < s.length; i++) {
    if(s[i] === "e"){
       answer+=0;
       continue;
    }
    const distance = [];

    for (let j = 0; j < indexE.length; j++) {
      distance.push(Math.abs(i - indexE[j]));
    }
    if (parseInt(answer[i]) === 0) continue;
    answer += Math.min(...distance);
  }
  return answer;
}

let str = "teachermode";
console.log(solution(str, "e"));

• indexE 는 e의 인덱스들을 담을 배열이다.
• while 문을 통해 문자열 s에서 e를 순차적으로 찾고, 다 찾으면( === -1) 멈춘다.
• for 문을 이용해 문자열 s의 각 문자가 만약 e라면 바로 answer에 0을 붙여준다.
  • 그렇지 않다면 distanceE 배열에 있는 인덱스로부터 거리를 모두 distance 배열에 넣어주고, 그 중 가장 최솟값을 answer에 붙여준다.

결과로 문자열 10121012210 이 출력된다.

문제

하나의 while문과 중첩 for문까지, 너무 많은 반복문이 포함되어 있다.
이 코드로 당장 이 문제는 해결할 수 있겠지만, 더 긴 문자열이 주어지는 상황에서는 많은 시간을 잡아먹을 것이다.

사실, 처음 문제를 보고 indexOf 라는 메서드를 써야겠다. 라는 생각에 사로잡혀 있었다.
그렇기 때문에 자연스럽게 인덱스를 가져와서, 모든 e의 인덱스 중 가장 가까운 인덱스와의 거리를 구해보자. 라는 생각으로 이어졌던 듯 하다.

• 최근 계속 이러한 문제가 이어졌는데, 문제를 보면 꼭 메서드를 써야지~ 하는 생각이랄까..?
• 기초적인 원리에 대한 이해가 부족하다보니 더 메서드에 의존하려는 듯 하다.

다시 생각해보자.

문자열의 각 문자의 입장에서, e는 왼쪽에 있거나 오른쪽에 있다. 혹은 둘 다 있을 수 있다.
그 거리 중 최소 거리를 구해야 한다.
e의 입장에서 생각하면, e가 아닌 다른 문자들은 각각의 e의 왼쪽에 있거나 오른쪽에 있어야 한다.

• 문자의 e 기준의 왼쪽으로부터의 거리를 구하고, e 기준의 오른쪽으로부터의 거리도 구한다.
  • 두 거리 중 가장 최소의 거리를 각 문자와 e 사이의 최소거리 라고 할 수 있다.

새로운 풀이

1. 기준 문자 e로부터 얼마나 떨어져 있는지를 확인해야 한다.
   • 그러므로 문자열의 각 문자들의 왼쪽, 오른쪽에 e가 어디에 위치한지를 알아야 한다.
   • 해당 문자의 e로부터의 거리는 두 거리 중에 최소거리를 선택한다.
2. 1에 의하여, 문자열을 순회하면서 e의 왼쪽으로부터의 거리, 그리고 e의 오른쪽으로부터의 거리를 측정한다.
   • i = 0 ~ i = n // 그리고 i = n ~ i = 0 으로 순회하면 각각의 문자마다 2개의 거리 값이 생기므로, 이 중 최솟값을 채택한다.
3. e와의 거리를 측정하는 변수 값에 대해 순회 시 시작값( i = 0, 그리고 역 순회시 i = n-1)은 충분히 큰 값을 가져야 한다.
   • 예를 들어 1로 시작해버리면, tteacher 에서 첫번째 t의 최소거리 값이 1이 되버린다.
   • 문자열의 첫번째 문자는 e의 왼쪽으로부터의 거리를 최소값으로 가지며, 문자열의 마지막 문자는 e의 오른쪽으로부터 거리를 최소값으로 가진다.

function solution(str, target){
    let answer = [];
      let d = 1000;

      // 순회
    for(let x of str){
      if(x==target){
        d=0;
        answer.push(d);
      } else{
        d++;
        answer.push(d);
      }
    }

  // 역 순회
  d=1000;
  for(let i=str.length-1; i>=0; i--){
    if(str[i] === target) d=0;
    else{
      d++;
      answer[i] = Math.min(answer[i], d);
    }
  }
  return answer;
}

let str = "teachermode";
console.log(solution(str, "e"));

다음과 같이 작성했다.

• 문자열을 순회하면서, target을 만나면 변수 d(= distance)를 0으로 바꾼다.
  • 그렇지 않으면 d를 1씩 증가시킨다.
  • 이렇게 하면 e로부터 오른쪽으로 떨어진 거리가 배열에 기록된다.
• 그리고 문자열을 역순회 하면서, 위와 동일한 작업을 한다.
  • 이렇게 하면 e로부터 왼쪽으로 떨어진 거리를 변수 d가 가지고 있다.
  • 이 값을 따로 배열을 선언해서 넣어줘도 되지만, 바로 Math.max 함수를 이용해서 기존 배열의 값과 비교했다.
  • 기존의 배열 값(e로부터 오른쪽 거리)과 변수 d값(e로부터 왼쪽 거리) 중 최소거리가 배열에 남는다.

다음의 코드는 두 번의 순회만으로
정답 1 0 1 2 1 0 1 2 2 1 0 을 볼 수 있다.