[TIL] 4일차 - Jacoste 알고리즘

삼각 달팽이

function solution(n) {
    let ret = Array.from({length: n}, (v, idx) => {
        let arr = [];
        for (let i = 0; i <= idx; i++) arr.push(0);
        return arr;
    })
    let x = -1;
    let y = 0;
    let cnt = 1;
    let line = -1;
    while (n-- && ++line >= 0) {
        for (let j = 0; j <= n; j++) {
            line % 3 === 0 ? ++x : line % 3 === 1 ? ++y : (--x, --y)
            ret[x][y] = cnt++;
        }
    }
    return [].concat(...ret);
}

여기서 중요한건 가장 마지막줄이다.

return [].concat(...ret);

이 부분이 굉장히 인상적이었다.

처음에는 reduce에 spread operator(...)를 사용했었는데 소요시간이 2800ms까지 나왔었다.

return ret.reduce((acc, cur) => [...acc, ...cur]);

고민을 하다가 concat()으로 바꿔보니 소요시간이 900ms까지 줄어들었다. 이 부분은 forEach를 통해 새로운 배열을 만드는 경우와 비슷했다.

return ret.reduce((acc, cur) => acc.concat(cur));

그래서 찾아보다 보니 flat()이라는 함수가 있어서 이를 사용했고 결과가 90ms까지 줄어드는 것을 확인할 수 있었다.

return ret.flat();

하지만... 구글링을 하던 중에 놀라운 사실을 또 하나 보게 되었다. flat()은 느리다는 내용의 글이었다. 간편하게 쓸 수 있는 flat()은 브라우저에 최적화가 되어있지 않은 상태이기 때문에 [].concat()이 더 유리하다!
해서 수정한 코드가 다음과 같다.

return [].concat(...ret);

결과는 20ms였다.
2800ms에서 20ms까지 줄어들었다.

이중배열을 단일배열로 만드는 하나의 과정만 최적화시켰을 뿐인데 소요시간이 이렇게나 줄어들었다.
정말 javascript는 신기한 언어다.

참고

https://velog.io/@milkcoke/Javascript-Array.flat-%EC%9D%80-%EB%8A%90%EB%A6%AC%EB%8B%A4