가장 짧은 문자거리

YEONGHUN KO·2021년 11월 23일
0

ALGORITHMS - PRACTICE

목록 보기
6/50
post-thumbnail

1. 최단거리

정말 뒤통수 딱 한대 얻어맞는 알고리즘이었다. 반대로 loop한다음에 더 작은값이 저장되도록 하다니... 박수...

s과 t를 넣은 다음 s의 각 글자가 t와 얼마나 떨어져있는지 알아보는 것이다. t사이에 글자가 있다면 가까운 t와 거리를 측정한다.

function shortest(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;
}
//  shortest('teachermode', 'e'); //  1 0 1 2 1 0 1 2 2 1 0

그림을 그려가면서 해보면 더 쉽게 알 수 있다.

profile
'과연 이게 최선일까?' 끊임없이 생각하기

0개의 댓글