선생님 머리를 싸메고 풀어 봤습니다.

자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)

4. 문자거리

작성

245

혹시 이 코드를 더 효율적으로 짤 수 있는 방법이 있을까요?


/** 
 * @param { string } str
 * @param { string } x 
 * */

function solution(str, x) {

    const originStr = str.split('');
    const indexArr = [];
    const result = [];

    for (let i = 0; i < str.length; i++) {

        if (originStr[i] === x) {

            indexArr.push(i);
        }

    };

    for (let i = 0; i < originStr.length; i++) {

        const matchResult = [];
        for (let j = 0; j < indexArr.length; j++) {
            
            matchResult.push({
                val : Math.abs(indexArr[j] - i),
                idx: j
            });

        };

        result.push(matchResult.sort((a, b) => {
            return a.val - b.val
        })[0].val);

    };

    return result;
};

console.log(solution('teachermode', 'e'));

javascript 코딩-테스트

답변 2

김태원

지식공유자

안녕하세요^^

스스로 코드를 구현해보는게 정말 중요한데 잘 하신 코드입니다. 다만 영상의 방법보다는 시간복잡도가 떨어집니다. 영상의 방법도 잘 익히셔서 님이 짠 코드를 더 좋은 코드로 리팩토링 해보시면 좋겠습니다.

아래 인프런 AI가 답변을 잘 해놓은 것 같습니다. 참고하시면 좋겠습니다.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.
초도수님의 자바스크립트 코드 최적화에 관한 질문에 대해 답변드리겠습니다.

현재 코드는 각 문자마다 ‘e’ 문자와의 거리를 모두 계산하여 매번 정렬하는 방식으로 구현되어 있습니다. 이러한 접근법은 각 문자에 대해 모든 ‘e’ 문자와의 거리를 계산해야하므로 비효율적일 수 있습니다. 아래는 알고리즘의 효율성을 개선한 코드 예시입니다.

function optimizeSolution(str, x) {
    let p = 1000; // 충분히 큰 수로 초기화합니다.
    const result = [];

    // 왼쪽에서 오른쪽으로 탐색
    for (let i = 0; i < str.length; i++) {
        if (str[i] === x) {
            p = 0;
        } else {
            p++;
        }
        result[i] = p;
    }

    // 오른쪽에서 왼쪽으로 탐색
    p = 1000; // 다시 초기화합니다.
    for (let i = str.length - 1; i >= 0; i--) {
        if (str[i] === x) {
            p = 0;
        } else {
            p++;
        }
        result[i] = Math.min(result[i], p); // 기존 값과 비교하여 더 작은 값을 선택
    }

    return result;
}

위의 최적화된 코드는 각 문자에 대하여 두 번의 탐색을 통해 ‘e’ 문자와의 최소 거리를 계산합니다. 첫 번째 탐색은 왼쪽에서 오른쪽으로 진행하며, 두 번째 탐색은 오른쪽에서 왼쪽으로 진행합니다. 이런 식으로 두 번의 선형 탐색만으로 각 문자와 ‘e’의 최소 거리를 구할 수 있으며, 시간 복잡도는 O(N)으로 개선됩니다.

코드의 효율성을 높이려면, 가능한 한 불필요한 반복을 줄이고, 문제의 특성을 활용하여 최적화하는 것을 고려해야 합니다. 제시한 최적화 방법이 초도수님의 코드 개선에 도움이 되었기를 바랍니다.

인프런 커뮤니티 질문&답변

선생님 머리를 싸메고 풀어 봤습니다.