[문자열탐색] 가장 짧은 문자거리

자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다.

 

 

 

 

📋 문제

한 개의 문자열 s와 문자 t가 주어지면 문자열 s의 각 문자가 문자 t와 떨어진 최소 거리를 출력한다.

 

 

👉 입력

길이가 100을 넘지 않는 문자열 s와 문자 t가 주어진다.

문자열과 문자는 소문자로 이루어진다.

 

 

👈 출력

문자열 s의 각 문자가 문자 t와 떨어진 최소 거리를 순서대로 출력한다.

 

 

📝 풀이

 

function solution(s, t) {
    let answer = [];
    let pos = s.indexOf(t);
    let arr_pos = [];
    let distance = [];

    while (pos !== -1) {
        arr_pos.push(pos);
        pos = s.indexOf(t, pos + 1)
    }

    for (let i = 0; i < s.length; i++) {
        if (s[i] === t) answer.push(0);
        else {
            distance = [];
            for (const idx of arr_pos) {
                distance.push(Math.abs(idx - i))
            }
            answer.push(Math.min(...distance))
        }
    }
    return answer;
}
let str = "teachermode";
console.log(solution(str, 'e'));

 

변수 pos에 문자열 s에서 최초로 등장한 문자 t의 인덱스를 저장한다.

이후 문자열 s에서 문자 t가 등장하지 않을 때까지 배열 arr_pos에 t의 인덱스 번호를 저장한다.

 

이후 for문을 돌며 s의 문자가 t와 같으면 정답을 저장할 배열인 answer에 0을 넣는다.

s의 문자가 t와 같지 않다면 t의 인덱스 번호를 저장한 arr_pos 배열을 순회하며 s와 t들 사이의 거리를 distance 배열에 저장한다.

그리고 이 중 제일 작은 값을 정답 배열인 answer에 넣는다.

 

처음에는 문제만 보고 이렇게 풀었는데 풀고 보니 문자열 s의 순회를 3번이나 하고 있다.

이 방법은 별로 좋지는 않은 듯 하다.

 

 

function solution(s, t) {
    let answer = [];
    let num = 1000;

    for (const a of s) {
        if (a === t) num = 0;
        else num++;
        answer.push(num);
    }

    num = 1000;
    for (let i = s.length - 1; i >= 0; i--) {
        if (s[i] === t) num = 0;
        else num++;
        answer[i] = Math.min(answer[i], num)
    }

    return answer;
}
let str = "teachermode";
console.log(solution(str, 'e'));

 

임의의 큰 값을 num이라는 변수에 넣는다.

여기서는 문자열의 길이가 100을 넘지 않기 때문에 임의의 큰 값으로 1000을 넣어주었다.

 

s의 각 문자를 순회하며 t와 같으면 num을 0으로 초기화하고 다르면 num에 1을 더한다.

해당 작업이 끝날 때마자 배열 answer에 num을 넣어준다.

 

다시 num의 값을 1000으로 초기화하고 for문을 돌며 s의 각 문자를 순회하는데 이때는 s를 거꾸로 순회한다.

위와 동일하게 s의 문자가 t와 같으면 num 값을 0으로 초기화하고 다르면 num에 1을 더한다.

위와 다른 점은 answer에 push하는 것이 아니라 위쪽 for문을 돌며 저장한 값과 현재의 num값을 비교해 더 작은 값을 answer[i]에 넣어주는 것이다.

 

즉, 첫 번째 for문에서는 각 문자의 왼쪽에 있는 t와의 거리를 측정하고 두 번째 for문에서는 각 문자의 오른쪽에 있는 t와의 거리를 측정해 둘 중 최솟값을 찾는 것이다.