LeetCode [JS] > 1496. Path Crossing

문제링크

https://leetcode.com/problems/path-crossing/description/

문제풀이

이 문제는 Set 객체를 이용하면 쉽게 풀 수 있다. Set 객체는 얼핏 보면 Array형태라고 생각될 수 도 있는데 HashTable 형태를 띄고 있기에 시간복잡도 차원에서 Array보다 훨씬 좋다. ( Set 객체는 내부적으로 key와 value가 동일한 구조이며 add되는 순서가 보장된다 그리고 iterable 하기에 순회함수를 쓰기에도 좋다 ). 해당 문제의 시간 복잡도는 O(n) 이다.  

/**
 * @param {string} path
 * @return {boolean}
 */
var isPathCrossing = function (path) {
    let position = [0, 0];
    let set = new Set();

    set.add("0,0");

    for (const direction of path) {
        if (direction === "N") {
            ++position[0];
        } else if (direction === "S") {
            --position[0];
        } else if (direction === "E") {
            ++position[1];
        } else if (direction === "W") {
            --position[1];
        }

        let str = position[0] + "," + position[1];
        let size = set.size;
        set.add(str);

        if (size === set.size) {
            return true;
        }
    }

    return false;
};