[문자열 탐색][JS] 가장 짧은 문자거리

Teasan·2022년 6월 29일

Algorythm 문자열탐색 알고리즘

Algorythm

목록 보기

7/17

가장 짧은 문자거리

문제 설명

한 개의 문자열 s와 문자 t가 주어지면 문자열 s의 각 문자가 문자 t와 떨어진 최소거리를 출 력하는 프로그램을 작성하세요.

입력 설명

첫 번째 줄에 문자열 s와 문자 t가 주어진다. 문자열과 문자는 소문자로만 주어집니다. 문자열의 길이는 100을 넘지 않는다.

출력 설명

첫 번째 줄에 각 문자열 s의 각 문자가 문자 t와 떨어진 거리를 순서대로 출력한다.

입출력 예제

▣ 입력예제 1

teachermode e

▣ 출력예제 1

10121012210

해답/풀이(내가 푼 문제)

function solution(str, text) {
  let answer = [];
  let first = 1000;

  for (let x of str) {
    if (x === text) {
      first = 0;
      answer.push(first);
    } else {
      first++;
      answer.push(first);
    }
  }

  first = 1000; // 초기화

  for (let i = str.length - 1; i >= 0; i--) {
    if (str[i] === text) {
      first = 0;
    } else {
      first++;
      answer[i] = Math.min(answer[i], first);
    }
  }
  return answer;
}

let str = "teachermode";
console.log(solution(str, "e")); // [1, 0, 1, 2, 1, 0, 1, 2, 2, 1, 0]

출력

[1, 0, 1, 2, 1, 0, 1, 2, 2, 1, 0]

해답/풀이(강의)

function solution(s, t) {
  let answer = [];
  let p = 1000;
  for (let x of s) {
    if (x === t) {
      p = 0;
      answer.push(p);
    } else {
      p++;
      answer.push(p);
    }
  }
  p = 1000;

  for (let i = s.length - 1; i >= 0; i--) {
    if (s[i] === t) {
      p = 0;
    } else {
      p++;
      answer[i] = Math.min(answer[i], p);
    }
  }

  return answer;
}

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

출력

[1, 0, 1, 2, 1, 0, 1, 2, 2, 1, 0]

수도 코드

function solution(s, t) {
  let answer = [];
  let p = 1000;
  // console.log(t); // e
  for (let x of s) {
    // console.log(x);
    if (x === t) {
      // x가 "e"와 같다면
      p = 0;
      answer.push(p);
    } else {
      // x가 "e"와 같지 않다면
      p++;
      answer.push(p);
    }
    // [1001, 0, 1, 2, 3, 0, 1, 2, 3, 4, 0]
  }
  // p는 다시 초기화 해준다.
  p = 1000;

  // s를 거꾸로 하나씩 돈다. (e, d, o, m, r, e, h ...)
  for (let i = s.length - 1; i >= 0; i--) {
    // console.log("i", s[i]); (e, d, o, m, r, e, h ...)
    if (s[i] === t) {
      p = 0;
    } else {
      p++;
      answer[i] = Math.min(answer[i], p);
    }
    // [1, 0, 1, 2, 1, 0, 1, 2, 2, 1, 0]
  }

  return answer;
}

let str = "teachermode";
console.log(solution(str, "e")); // [1, 0, 1, 2, 1, 0, 1, 2, 2, 1, 0]

풀이 순서

먼저 주어진 문자열 s와 t를 살펴보자.

let str = "teachermode";
solution(str, "e");

문자열 s("teachermode")에서 "e" 를 찾아 s 문자열 각각의 문자와 "e"의 거리(최소)계산해주면 되는 걸 알 수 있다.

let answer = [];

배열에 담아 반환할 예정이기 때문에, 최종 반환 값 answer 에 빈 배열을 할당한다.

let p = 1000;

s 문자열 각각의 문자와 "e"의 거리를 카운팅 해줄 변수 p를 생성한다. p에 1000을 할당하는 이유는 문자열 teachermode의 가장 첫번째 문자인 't'에는 왼쪽 타켓 문자인 'e'가 없기 때문에 이 왼쪽 타켓 문자("e")와의 거리를 대충 큰 숫자로 정하여 오른쪽 타켓 문자와의 거리가 채택되게 하려고 적당히 큰 숫자인 1000으로 할당한 것이다.

t **e** a c h **e** r m o d **e**

일단 p가 1000에서 시작한다는 기준으로 카운팅 했을 때 for 문을 정방향으로 돌아 계산해보면 이렇다.

for (let x of s) {
  if (x === t) {
    // x가 "e"와 같다면
    p = 0;
    answer.push(p);
  } else {
    // x가 "e"와 같지 않다면
    p++;
    answer.push(p);
  }
  // [1001, 0, 1, 2, 3, 0, 1, 2, 3, 4, 0]
}

answer에 push 해준 값을 콘솔로그에 찍어보면 이런 결과값이 나온다.

t **e** a c h **e** r m o d **e**
1001 **0** 1 2 3 **0** 1 2 3 4 **0**

s 문자열 각각의 문자와 "e"의 최소 거리를 구하기 위해서는 다시 for 문을 역방향으로 돌면서 최소 값을 구해야 한다. 두 번째 for 문을 돌기 전 다시 p를 1000으로 초기화해주고,

let p = 1000;

역방향 for 문 안에서 +1을 하면서 정방향으로 돌았을 때와 비교했을 때 더 작은 값으로 할당한다.

// s를 거꾸로 하나씩 돈다. (e, d, o, m, r, e, h ...)
for (let i = s.length - 1; i >= 0; i--) {
  // console.log("i", s[i]); (e, d, o, m, r, e, h ...)
  if (s[i] === t) {
    p = 0;
    // 이미 위에서 answer의 갯수를 맞췄기 때문에 여기서 다시 answer.push(p)를 할 필요가 없다.
  } else {
  }
}

s 문자열 각각의 문자와 "e"의 최소 거리를 구하기 위해서는 이 두개의 for 문으로 돌려서 카운팅한 p와 answer[i]([1001, 0, 1, 2, 3, 0, 1, 2, 3, 4, 0]) 를 비교했을 때 가장 작은 값(Math.min())을 구해서 반환해야 할 것이다.

// s를 거꾸로 하나씩 돈다. (e, d, o, m, r, e, h ...)
for (let i = s.length - 1; i >= 0; i--) {
  // console.log("i", s[i]); (e, d, o, m, r, e, h ...)
  if (s[i] === t) {
    p = 0;
  } else {
    p++;
    // answer = [1001, 0, 1, 2, 3, 0, 1, 2, 3, 4, 0]
    answer[i] = Math.min(answer[i], p);
  }
  // [1, 0, 1, 2, 1, 0, 1, 2, 2, 1, 0]
}