알고리즘, 자료구조/IDEA note

어느 것과 더 가까운지에 대해서

fe-sanginjeong 2025. 5. 12. 08:00

문자열이 있다고 치자. 그리고 이 문자열의 각 문자들이 특정 문자와의 거리(가까운 거리)를 구해야 한다.

 

이해하기 쉽게 예시로 teachermode라는 문자열이 있고 특정 문자 e가 입력되면, 출력은

1 0 1 2 1 0 1 2 2 1 0 이다.

 

나는 처음에 문자열의 각 문자를 같은 문자열의 다른 문자와 비교해야하므로 무조건 이중 for문을 써야할 수 밖에 없다고 생각해서 아래와 같이 풀었다.

function solution(s,t){
  const answer = [];
  for(let i=0; i<s.length; i++){
    let min_distance = Number.MAX_SAFE_INTEGER;
    for(let j=0; j<s.length; j++){
      if(s[j] === t){
        const distance = Math.abs(i-j);
        if(distance < min_distance) min_distance = distance;
      }
    }
    answer.push(min_distance);
  }

  return answer.join(" ")
}

 

 

IDEA : 왼쪽에서부터의 거리와 오른쪽에서부터의 거리를 각각 검사하고, 작은것들로 취합.

function solution(s,t) {
  const answer = [];
  let p = 100;
  for(let i=0; i<s.length; i++){
    if(s[i] === t) {
      p = 0;
      answer.push(p);
    } else {
      p++;
      answer.push(p);
    }
  }

  p = 100;
  for(let i=s.length-1; i>=0; i--){
    if(s[i] === t) p=0;
    else {
      p++;
      answer[i] = Math.min(p, answer[i]); // 원래있던 왼쪽에서와의 거리와 현재 오른쪽에서와의 거리중 작은값
    }
  }
  return answer.join(" ")
}