1260. Shift 2D Grid

💡풀이

// Discussion의 방법
var shiftGrid = function (grid, k) {
  const len = grid[0].length;
  const arr = grid.flat();
  const result = [];

  while (k-- > 0) arr.unshift(arr.pop());

  for (let i = 0; i < arr.length; i += len) {
    result.push(arr.slice(i, i + len));
  }

  return result;
};

let grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
  ],
  k = 1;
shiftGrid(grid, k);

let ransomNote = 'aabb';
let magazine = 'aabbc';
canConstruct(ransomNote, magazine);

/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number[][]}
 */

// 스터디원 중 한 분의 방법(One pass) - 설명이 매우 자세하다!
var shiftGrid = function (grid, k) {
    /**
     * grid에 있는 모든 숫자를 한번씩만 봐서 정답을 유추하는 방법입니다
     * grid[i][j]가 ans에 어디로 가야 하는지 알아내 정답을 만들어 냅니다
     */

    // m = 세로 길이
    // n = 가로 길이
    const m = grid.length;
    const n = grid[0].length;

    // k 를 m * n보더 적게 줄입니다
    // 예를 들어, grid크기가 9인데 k가 10이면 k를 1로 줄입니다.
    k %= m * n;

    // k가 0이면 grid를 그대로 리턴합니다
    if (k == 0) {
        return grid;
    }

    // ans이란 2d array를 하나 만듭니다
    const ans = new Array(m).fill(0).map(() => new Array(n).fill(0));

    // 이제 grid의 모든 숫자를 돌아봅니다
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // grid[i][j]가 ans의 어디에 들어가야 하는지 계산합니다
            // j에 k를 더해 i와 j를 다듬으면 됩니다
            let newI = i;
            let newJ = j + k;
            while (newJ >= n) {
                newI++;
                newJ -= n;
            }
            if (newI >= m) {
                newI -= m;
            }

            // ans에 grid[i][j]를 넣습니다
            ans[newI][newJ] = grid[i][j];
        }
    }

    // ans를 리턴합니다
    return ans;
};

// 같은 분의 방법입니다.(in-place: 공간 복잡도 측면에서 위의 방법보다 효율적임)
/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number[][]}
 */
var shiftGrid = function (grid, k) {
    /**
     * grid안에서 해결 다 하는 방식입니다.
     */

    // grid = [
    //     [1, 2, 3],
    //     [4, 5, 6],
    //     [7, 8, 9]
    // ] 와 k = 3 이면,

    // 1. grid를 뒤바꾸고,
    // grid = [
    //     [9, 8, 7],
    //     [6, 5, 4],
    //     [3, 2, 1]
    // ]

    // 2. 뒤바뀐 grid에 앞 k 숫자들을 뒤바꾸고,
    // grid = [
    //     [7, 8, 9],
    //     [6, 5, 4],
    //     [3, 2, 1]
    // ]

    // 3. 나머지 숫자들도 바꿉니다
    // grid = [
    //     [7, 8, 9],
    //     [1, 2, 3],
    //     [4, 5, 6]
    // ]

    // 쨔잔

    const m = grid.length;
    const n = grid[0].length;

    k %= m * n;

    if (k == 0) {
        return grid;
    }

    const size = m * n;

    reverse(grid, 0, size - 1);
    reverse(grid, 0, k - 1);
    reverse(grid, k, size - 1);

    return grid;
};

/**
 * Reverse grid contents in place from start to end inclusively
 * @param {number[][]} grid
 * @param {number} start
 * @param {number} end
 */
var reverse = function (grid, start, end) {
    const n = grid[0].length;

    let leftI = 0;
    let leftJ = start;

    while (leftJ >= n) {
        leftI++;
        leftJ -= n;
    }

    let rightI = 0;
    let rightJ = end;

    while (rightJ >= n) {
        rightI++;
        rightJ -= n;
    }

    while (leftI * n + leftJ < rightI * n + rightJ) {
        [grid[leftI][leftJ], grid[rightI][rightJ]] = [
            grid[rightI][rightJ],
            grid[leftI][leftJ],
        ];

        if (++leftJ >= n) {
            leftI++;
            leftJ -= n;
        }

        if (--rightJ < 0) {
            rightI--;
            rightJ += n;
        }
    }
};

📝정리

• Grid 문제다. 결국 혼자 못 풀고 Discussion의 도움을 받았다. 이 쪽 문제를 내가 좀 힘들어해서.. 다른 스터디원분이 더 풀어볼 수 있는 문제를 추천해주셨다! 감사합니다 :)

• 뒤의 두 방법은 다른 스터디원 분께서 해결하셨던 두 가지 방법이다. 자세한 설명은 주석에 스터디원분이 미리 작성을 하셨으니 참고하면 될 것 같다.

문제 링크

https://leetcode.com/problems/shift-2d-grid/

LeetCode GitHub

https://github.com/tTab1204/LeetCode/tree/main/%EC%A3%BC%EC%98%81