JavaScript로 문자열에서 특정 문자까지의 최단 거리 구하기

문제 개요

영어 소문자 알파벳으로만 이루어진 문자열 str과, 해당 문자열 안에 반드시 존재하는 단일 문자 char를 인수로 받는 JavaScript 함수를 작성해야 합니다.

함수는 문자열 str의 각 문자에 대해, char로 지정된 문자 중 자신과 가장 가까운 것까지의 거리를 담은 배열을 생성하여 반환해야 합니다.

입력 · 출력 예시

예를 들어 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

입력

const str = 'somestring';
const char = 's';

출력

const output = [0, 1, 2, 1, 0, 1, 2, 3, 4, 5];

0번째와 4번째 인덱스는 's' 그 자체이므로 거리가 0입니다. 나머지 문자들은 왼쪽 또는 오른쪽에 있는 가장 가까운 's'까지의 거리를 값으로 갖습니다. 예를 들어 마지막 문자 'g'(인덱스 9)는 가장 가까운 's'가 인덱스 4에 있으므로 거리가 5가 됩니다.

접근 방법: 양방향 순회(Two-Pass)

이 문제를 효율적으로 해결하려면 배열을 두 번 순회하는 방식이 유용합니다.

왼쪽 → 오른쪽 순회: 각 위치에서 왼쪽 방향에 있는 가장 가까운 목표 문자까지의 거리를 계산합니다.
오른쪽 → 왼쪽 순회: 같은 로직을 반대 방향으로 수행하며, 기존 값보다 더 가까운 거리가 있으면 갱신합니다.

정답은 항상 두 방향 순회 결과 중 최솟값이므로, 두 번의 순회만으로 모든 위치에 대한 거리를 구할 수 있습니다. 시간 복잡도는 O(n)이며, 결과 배열을 제외한 추가 공간은 O(1)입니다.

구현 코드

다음은 위 접근 방식을 구현한 전체 코드입니다.

const str = 'somestring';
const char = 's';
const shortestDistance = (str = '', char = '') => {
   const res = new Array(str.length).fill(Infinity)
   let prev = Infinity
   const handleIndex = (i) => {
      if (str[i] === char) {
         prev = i
      }
      res[i] = Math.min(res[i], Math.abs(i - prev))
   }
   for (let i = 0; i < str.length; i++) {
      handleIndex(i)
   }
   prev = Infinity
   for (let i = str.length - 1; i >= 0; i--) {
      handleIndex(i)
   }
   return res
}
console.log(shortestDistance(str, char));

실행 결과

[ 0, 1, 2, 1, 0, 1, 2, 3, 4, 5 ]

코드 동작 원리

res: 각 인덱스별 최단 거리를 저장할 배열로, 초기값은 무한대(Infinity)입니다.
prev: 직전에 발견한 목표 문자의 인덱스를 추적하며, 아직 발견되지 않았으면 무한대로 둡니다.
handleIndex: 현재 문자가 목표 문자라면 prev를 현재 인덱스로 갱신하고, 현재 위치와 prev 사이의 거리를 계산해 기존 값과 비교한 뒤 더 작은 값을 저장합니다.
첫 번째 순회가 끝나면 prev를 다시 무한대로 초기화한 뒤, 오른쪽에서 왼쪽으로 두 번째 순회를 진행합니다.

이렇게 하면 각 문자 위치에서 좌우 어느 쪽이든 가장 가까운 목표 문자까지의 거리를 정확하게 구할 수 있습니다.