[알고리즘-JS] 짧은 문자 거리 구하기

문제

문자열(s)과 특정 문자(t)가 입력되면 각 문자와 특정 문자(t)와의 거리 중 가장 짧은 거리를 숫자로 출력하시오.

 

입력 예제

asakeisjeisns
s

 

출력 예제

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

 

 

 

 

 

풀이

정방향으로 거리 수치를 담고, 역방향으로 다시 오면서 이전 값과 비교했을 때 더 작은 값이 나오면 교체한다.

정방향에서 맨 처음 문자와 역방향에서 맨 마지막 문자는 거리 수치를 구할 수 없기 때문에 가장 큰 정수로 초기화한다.
그렇게 되면 맨 처음 문자는 역방향에서 측정된 거리를 사용하게 되고, 마지막 문자는 정방향에서 측정된 거리를 사용하게 된다.

 

function solution(s, t) {
  let answer = [];
  let p = Number.MAX_SAFE_INTEGER;

  // 정방향
  for (let x of s) {
    if(x === t) {
      p = 0;
      answer.push(p);
    }
    else {
      p++;
      answer.push(p);
    }
  }

  console.log(answer); // [9007199254740992, 0, 1, 2, 3, 0, 1, 0]

  // 초기화
  p = Number.MAX_SAFE_INTEGER;

  // 역방향
  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; // [1, 0, 1, 2, 1, 0, 1, 0]
}


console.log(solution("asakisns", "s"));