문자열 탐색 - 가장 짧은 문자거리

문자열 s와 문자 t가 주어졌을 때, 문자열 s의 각 문자가 t와 떨어진 최소거리를 구하는 문제이다.

 

내 풀이

생각한 풀이 방법은 다음과 같다.

먼저 문자열 s에서 t가 위치한 인덱스를 배열에 저장을 한다. 그리고 문자열을 순회하면서 문자열의 각 문자마다 t의 인덱스가 저장된 배열을 순회하며 인덱스끼리의 차이를 구해 최솟값을 구하는 것이다.

function solution(s, t) {
  const result = [];
  const tmp = [];
  [...s].forEach((c, i) => {
    if (c === t) tmp.push(i);
  });

  [...s].forEach((_, i) => {
    let min = Number.MAX_SAFE_INTEGER;
    tmp.forEach((n) => {
      min = Math.min(min, Math.abs(i - n));
    });
    result.push(min);
  });

  return result.join(' ');
}

let str = 'teachermod';
console.log(solution(str, 'e'));

 

위의 풀이로도 문제는 풀 수 있었지만 최악의 경우에는 시간 복잡도가 O(N^2)이 될 수 있기 때문에 비효율적인 풀이라는 생각이 들었다.

 

강의 풀이

문자열이 다음과 같이 주어지고, 각 문자들이 e와 떨어져있는 거리의 최솟값을 구한다고 가정하자.

각 문자들의 입장에서 왼쪽에서부터 e와 떨어진 거리와 오른쪽에서부터 e와 떨어진 거리의 최솟값을 구하면 된다.

t

e

a

c

h

e

r

m

o

d

 

M은 최솟값을 구하기 위한 큰 수라고 가정하자.

 

오른쪽으로부터 t와 떨어진 거리 : 1 0 3 2 1 0 M M M M 

왼쪽으로부터 t와 떨어진 거리 : M 0 1 2 3 0 1 2 3 4

정답 : 1 0 1 2 1 0 1 2 3 4

function solution(s, t) {
  const result = [];
  let tmp = 1000;
  for (const c of s) {
    if (c === t) tmp = 0;
    else tmp += 1;
    result.push(tmp);
  }
  tmp = 1000;
  for (let i = s.length - 1; i >= 0; i--) {
    if (s[i] === t) tmp = 0;
    else {
      tmp += 1;
      result[i] = Math.min(result[i], tmp);
    }
  }

  return result;
}

 

O(N)으로 효율성을 높일 수 있다.