2023-09-21 일자 알고리즘 공부

js 자바스크립트 알고리즘 공부를 하고 배운점을 정리한 게시글 입니다.

1.가장 짧은 문자거리

문제 :한 개의 문자열 s와 문자 t가 주어지면 문자열 s의 각 문자가 문자 t와 떨어진 최소거리를 출력하는 프로그램을 작성하세요.

첫 번째 줄에 문자열 s와 문자 t가 주어진다.
문자열과 문자는 소문자로만 주어집니다.
문자열의 길이는 100을 넘지 않는다.

코드

function sol(arr, s) {
  let answer = [],
    p = 1000;
  for (let x of arr) {
    if (x !== s) {
      p++;
      answer.push(p);
    } else {
      p = 0;
      answer.push(p);
    }
  }
  p = 1000;
  for (let i = 0; i < arr.length; i++) {
    if (arr[arr.length - i - 1] !== s) {
      p++;
      if (p < answer[arr.length - i - 1]) {
        answer[arr.length - i - 1] = Math.min(answer[arr.length - i - 1], p);
      }
    } else {
      p = 0;
    }
  }
  return answer;
}
console.log(sol('teachermode', 'e'));

// 선생님 코드

function solution(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;
}

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

풀이: 비슷하게 문제를 풀었지만 다른부분은 for문이 맨끝에서 부터 도는부분이 조금 다릅니다.
먼저, 문제에서 문자열을 주고 특정 문자 하나를 줍니다. 그리고
특정 문자와 문자간의 이격거리를 구하는 알고리즘 문제입니다.
앞에서 탐색 한번을 하고 또 뒤에서 탐색 한번을 해서 풀 수 있는 문제입니다.
일단 거리를 담기 위해서 answer 을 array로 만들어줬습니다.
그리고 문자열의 길이가 100 넘지 않는다 라는 조건 때문에 100보다 큰 숫자인 1000인 p라는 변수를 만들어줬습니다.
그리고 for of 문을 돌려서 x와 특정문자가 같지 않다면 p 를 ++ 해주고
answer에 push 해줍니다.
같을땐 p를 0으로 만들어주고 answer에 푸쉬해줍니다.
이렇게 되면
[1001,1,2,0,1,2,3,4,0] 이런식으로 배열이 생깁니다.
그리고 다시 뒤에서 부터 탐색을 하기 위해 for문을 다시 돌립니다.
이때 p는 다시 초기값인 1000으로 바꿔줍니다.
for문이 돌면서 (arr[arr.length -i -1]) 이랑 s가 다르다면 p를 다시 카운팅 시켜주고
p가 arr의 인덱스의 값보다 작을때만 answer[arr.length -i -1] = 뒷자리 인덱스의 값을 Math.min() 을 이용해 인덱스의 값과 p를 비교하여 더 작은 숫자를 할당 시켜줍니다.
위에와 똑같이 s와 answer[인덱스]의 값이 같다면 p를 0으로 바꿔줍니다.