[JS.알고리즘] 문자 거리 출력

📘문제설명

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

출력

10121012210

풀이

const solve = (s, t) => { 
    // teachermode , e
    const answer = [];
    
    let count = 100;
    let backCount = 100;
    for(let i = 0; i < s.length; i ++) {
      if (s[i] === t) {
        count = 0;
        answer.push(count); 
      } else {
        count ++;
        answer.push(count)
      }
    }
    for (let j = s.length - 1; j >= 0; j--) {
      if (s[j] === t) {
        backCount = 0;
        continue;
      } else {
        backCount ++;
        answer[j] = Math.min(answer[j], backCount)
      }
    }
    return answer
  }

solve('teachermode','e')

풀이를 보면 count, backCount 를 나눠놨는데 사실 그럴 필요 없이 초기화 해줬으면 된다고 생각한다.

위에 for 문 부터 보면, 처음에 t 문자열과 같은지 확인 한 후, 아닐 경우 카운트를 증가시켜서 배열에 담아준다

앞에서 부터 쭉 뒤로 그다음 뒤에서 부터 앞으로 가면서 같지 않을 경우 비교를 해서 작은 값을 넣어준다.

해당 문제는 o(n) 시간복잡도를 가진다 반복문이 두번이라 o(2n) 아니냐고 할수 있지만
계수는 날려도 무방하다.