행렬 테두리 회전하기

문제 접근

숫자를 가진 행렬을 2차원 배열을 이용해, 특정한 규칙으로 구현하는 문제이다.

사실 내가 어려워하는 유형인데, 우선 세부적인 내용을 구현해야 하기 때문에, 시간이 소모되고, 특히 2차원 배열이 난 좀 헷갈린다.

난 이 문제를 다음과 같이 접근했다.

• 숫자 행렬 저장: 각 쿼리마다, 움직인 숫자 행렬을 기억해야 하기 때문에 하나의 2차원 배열에 숫자 행렬을 저장해야 했다.

for (let i = 0; i < rows * columns; i++) {
    const numArr = Array(rows * columns)
    numArr[i] += i + 1
  }
  const totalArr = [[0]]
  for (let j = 1; j <= rows; j++) {
    const arr = [0]
    for (let k = 1 + (j - 1) * columns; k <= j * columns; k++) {
      arr.push(k)
    }
    totalArr.push(arr)
  }

• 위쪽 가로, 아래쪽 가로, 윈쪽 세로, 오른쪽 세로로 문제 나누기: 이 네 가지 경우로 나누어 각각의 변이 어떻게 바뀌는지 보았다.

queries.forEach((query) => {
    const newTotalArr = totalArr.map((e) => [...e])
    const [x1, y1, x2, y2] = query
    let minArr = []
    // 위쪽 가로
    totalArr[x1][y1] = newTotalArr[x1 + 1][y1]
    minArr.push(totalArr[x1][y1])
    for (let i = y1 + 1; i <= y2; i++) {
      totalArr[x1][i] = newTotalArr[x1][i - 1]
      minArr.push(totalArr[x1][i])
    }
    // 아래쪽 가로
    totalArr[x2][y2] = newTotalArr[x2 - 1][y2]
    minArr.push(totalArr[x2][y2])
    for (let i = y1; i <= y2 - 1; i++) {
      totalArr[x2][i] = newTotalArr[x2][i + 1]
      minArr.push(totalArr[x2][i])
    }
    // 왼쪽 세로
    totalArr[x2][y1] = newTotalArr[x2][y1 + 1]
    minArr.push(totalArr[x2][y1])
    for (let i = x1; i <= x2 - 1; i++) {
      totalArr[i][y1] = newTotalArr[i + 1][y1]
      minArr.push(totalArr[i][y1])
    }
    // 오른쪽 세로
    totalArr[x1][y2] = newTotalArr[x1][y2 - 1]
    minArr.push(totalArr[x1][y2])
    for (let i = x1 + 1; i <= x2; i++) {
      totalArr[i][y2] = newTotalArr[i - 1][y2]
      minArr.push(totalArr[i][y2])
    }

• 숫자 행렬 배열 깊은 복사: 이 문제는 상대적인 위치가 변하는 문제이다. 그러므로 같은 2차원 배열 안 요소간의 값의 변화가 일어나야 하는데, 2차원 배열인 1개 뿐이면 값의 일방적인 변화만 일어난다. (ex. totalArr[1][2] = totalArr[1][1] 면 이제 totalArr[1][2] 값 추적 불가)
  따라서 2차원 배열이 같은 값이지만, 참조값이 다른 깊은 복사를 다음과 같이 진행했다.

const newTotalArr = totalArr.map((e) => [...e])

• 최소값 구하기: 배열에 저장 후 정렬을 통해 구했다.

minArr.sort((a, b) => a - b)
    minValueArr.push(minArr[0])

문제 해결

function solution(rows, columns, queries) {
  for (let i = 0; i < rows * columns; i++) {
    const numArr = Array(rows * columns)
    numArr[i] += i + 1
  }
  const totalArr = [[0]]
  for (let j = 1; j <= rows; j++) {
    const arr = [0]
    for (let k = 1 + (j - 1) * columns; k <= j * columns; k++) {
      arr.push(k)
    }
    totalArr.push(arr)
  }
  const minValueArr = []
  queries.forEach((query) => {
    const newTotalArr = totalArr.map((e) => [...e])
    const [x1, y1, x2, y2] = query
    let minArr = []
    // 위쪽 가로
    totalArr[x1][y1] = newTotalArr[x1 + 1][y1]
    minArr.push(totalArr[x1][y1])
    for (let i = y1 + 1; i <= y2; i++) {
      totalArr[x1][i] = newTotalArr[x1][i - 1]
      minArr.push(totalArr[x1][i])
    }
    // 아래쪽 가로
    totalArr[x2][y2] = newTotalArr[x2 - 1][y2]
    minArr.push(totalArr[x2][y2])
    for (let i = y1; i <= y2 - 1; i++) {
      totalArr[x2][i] = newTotalArr[x2][i + 1]
      minArr.push(totalArr[x2][i])
    }
    // 왼쪽 세로
    totalArr[x2][y1] = newTotalArr[x2][y1 + 1]
    minArr.push(totalArr[x2][y1])
    for (let i = x1; i <= x2 - 1; i++) {
      totalArr[i][y1] = newTotalArr[i + 1][y1]
      minArr.push(totalArr[i][y1])
    }
    // 오른쪽 세로
    totalArr[x1][y2] = newTotalArr[x1][y2 - 1]
    minArr.push(totalArr[x1][y2])
    for (let i = x1 + 1; i <= x2; i++) {
      totalArr[i][y2] = newTotalArr[i - 1][y2]
      minArr.push(totalArr[i][y2])
    }
    minArr.sort((a, b) => a - b)
    minValueArr.push(minArr[0])
  })

  return minValueArr
}

느낀점

• 시간이 많이 걸렸다(1시간 반). 아직 이런 유형의 문제에 약하다는 생각이 든다.
• 이 접근법이 맞는지 다른 사람들의 풀이를 보며 생각해야겠다.

다른 접근법

• 기본적으로 비슷하지만, map을 2번 겹쳐서 2차원 배열을 간단히 만드는 법이 있다.

 const a = [...Array(rows)].map((_, r)=>[...Array(columns)].map((_, c)=>r*columns+c+1));

Reference
https://programmers.co.kr/learn/courses/30/lessons/77485/solution_groups?language=javascript