Array, Matrix

[dlehdanakf]

배열 만들기

• Array.prototype.push 메소드는 실행하는데 시간이 다소 소비되는 메소드이다.
• 따라서, 문제를 읽은 후 배열을 사용해야하는 문제임을 파악한 뒤, 배열의 최대 길이를 구할 수 있다면 미리 해당 공간만큼 확보된 배열을 선언하고 사용하는게 유리하다.
• DP 같은 문제를 해결할 때 미리 배열을 선언하게 되는데, 이 때 보통 0으로 초기화하게된다.

const n = 100000;

console.time('A');
const a = [];
for(let i = 0; i < n; i++) a.push(0);
console.timeEnd('A');

console.time('B');
const b = new Array(n).fill(0);
console.timeEnd('B');

// A: 45.643ms
// B: 1.554ms

• Array.prototype.fill 메소드를 사용하는게 훨씬 빠르다는 것을 확인할 수 있다.
• 하지만 new Map(), new Set() 같은 인스턴스로 초기화할 때는 fill 메소드를 사용할 수 없고 map 메소드가 들어갈 경우 시간은 비슷해진다.
• 원시 데이터타입으로 초기화할 때만 속도향상을 노릴 수 있는 셈

const n = 100000;

console.time('A');
const a = [];
for(let i = 0; i < n; i++) a.push(new Map);
console.timeEnd('A');

console.time('B');
const b = new Array(n).fill(undefined).map(_ => new Map);
console.timeEnd('B');

console.time('C');
const c = [...Array(n)].map(_ => new Map);
console.timeEnd('C');

console.time('D');
const d = new Array(n);
for(let i = 0; i < n; i++) d[i] = new Map;
console.timeEnd('D');

// A: 25.649ms
// B: 22.422ms
// C: 35.954ms
// D: 22.157ms

• 어떤 형태로 만들더라도 좋은 성능을 기대하긴 힘들다. 애초에 new Map() 자체가 느린걸 수도 있다...
• 위 소스코드에서 new Map() 을 제거하고 { } Object를 생성하는 코드로 바꾼 뒤 실행했더니 한결 빨라졌다.

A: 13.806ms
B: 3.195ms
C: 7.350ms
D: 10.878ms

행렬 회전시키기

• 가끔 2차원 배열 즉, 행렬을 가지고 이것저것 까다롭게 구는 문제들이 있다.
• 행렬을 가지고 회전했을 때 결과를 구하거나 다시 회전한 결과를 가지고 문제를 풀어야하는데 회전 하는 그 메소드만 구현하느라 시간을 낭비하는 것은 안타까운 일이다.

const rotate = matrix => {
  return matrix.map((row, i) =>
    row.map((val, j) => matrix[matrix.length - 1 - j][i])
  );
};

[dlehdanakf]

원소를 모두 더했을 때 n 이 되는 배열

• 프로그래머스 문제

const make = (target, length, sum = 0, trace = []) => {
    if(sum === target && trace.length === length) {
        console.log(trace);
    }
    if(trace.length >= length) {
        return;
    }

    const last = trace[trace.length - 1] || 1;
    const remain = target - sum;
    for(let i = last; i <= remain; i++) {
        make(target, length, sum + i, [...trace, i]);
    }
};

[dlehdanakf]

Transpose

• M × N 행렬이 있을 때 N × M 행렬로 바꿔주는 메소드
• 함수 코드가 좀 긴 것 같은데 더 짧게 코드를 작성하는 방법은 다음에 고민해보자.

const transpose = matrix => {
    const r = matrix.length, 
          c = matrix[0].length, 
          results = new Array(c).fill(undefined).map(_ => new Array(r));

    matrix.forEach((m, i) => m.forEach((n, j) => results[j][i] = n));
    return results;
};

• 행렬 matrix 변수를 인자로 받아서 행 개수와 열 개수를 구한다. 이 때 matrix의 열 개수는 모든 행에 대해 동일해야한다.
• Array.prototype.forEach 메소드를 돌면서 [i][j] 를 [j][i] 로 바꿔버려서 대입한다.