Longest Common Prefix

---

💬 문제

[문제 링크]

문자열이 들어있는 배열 strs
모든 요소가 공통으로 가지고 있는 가장 긴 접두사 구하여 반환
같은 문자로 시작하는 것이 없다면 빈 문자열 반환

✍️ 나의 풀이

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let prefix = strs[0];

    for (let i = 1; i < strs.length; i++) {
        const length = prefix.length < strs[i].length ? prefix.length : strs[i].length;
        let temp = '';
        for (let j = 0; j < length; j++) {
            if (prefix[j] === strs[i][j])
                temp += prefix[j]
            else
                break ;
        }
        if (temp === '')
            return temp;
        prefix = temp;
    }

    return prefix;
};

0번 인덱스 값을 prefix에 저장해두고 1번부터 비교 시작
값이 같은 문자는 temp에 추가하고 그렇지 않으면 비교 멈추기
temp가 빈문자열이었으면 공통 부분이 없는 것이므로 바로 빈 문자열 반환
그렇지 않으면 temp가 새 prefix가 되어 다음 문자열과 비교

📌 결과

Accepted
Runtime 68ms (Beats 9.73%)
Memory 51.61MB (Beats 10.78%)

📚 러닝 포인트

왜 slice를 안쓰고 알고리즘을 구현하려고 했을까...? 처음에 구상할 때는 안맞는 부분을 버려야지라고 생각했는데 하다가보니 맞는 부분을 새로 구성하는 방법으로 만들었다. 그러다보니 당연히 런타임과 메모리 효율이 최악으로 나왔다. 결과를 보고 더 좋은 접근법이 있는건지 둘러보니 역시 slice를 쓰는게 맞았다. 그러면 temp를 사용할 필요가 없어진다. 그리고 인덱스 접근으로 인한 참조 에러가 나지 않게 하려고 두 비교 대상의 문자열 길이 중 더 짧은 걸 기준으로 순회하려고 했는데 문자열의 인덱스는 길이를 초과해도 undefined가 나올 뿐 참조 에러는 발생하지 않았다! 그래서 length를 구하는 작업을 삭제하고 그냥 prefix의 length를 기준으로 하니 런타임이 훨씬 줄어들었다. 그래서 최종 수정본은 아래와 같다.

var longestCommonPrefix = function(strs) {
    let prefix = strs[0];

    for (let i = 1; i < strs.length; i++) {
        for (let j = 0; j < prefix.length; j++) {
            if (prefix[j] !== strs[i][j]) {
                prefix = prefix.slice(0, j);
                break ;
            }
        }
        if (prefix === '')
            return prefix;
    }

    return prefix;
};

이렇게하면 런타임 55ms(61.14%) / 메모리 49.55MB(52.09%)가 나온다.