[백준] 16927 배열 돌리기 2 (Javascript)

문제

BOJ16927_배열 돌리기 2

풀이

요구사항

$N \times M$ 크기의 2차원 배열을 반시계 방향으로 R 바퀴 돌려라.
하지만 R의 범위가 $1 \le R \le 10^9$이기 때문에 일일히 R번 회전시킬 경우 시간초과가 난다.

해결방안

배열을 굳이 R번 회전시킬 필요 없다.
arr[i][j]가 R번 회전했을 때 어느 위치로 가는지만 알 수 있다면, 이를 배열의 모든 원소에 적용시키면 된다.
그렇다면 R번 회전했을 때 어느 위치로 갈지는 어떻게 알 수 있을까?

나는 우선 배열의 외곽부를 1차원 배열로 만들기로 했다.

1차원 배열을 만들 때 회전 방향(반시계 방향)에 맞추어 값을 입력한다.

그리고 각각의 1차원 배열을 R번 회전시켰을 때의 위치를 계산하는 작업을 수행해준다.

위치를 계산하는 공식은 이렇다.

const len = (1차원 배열의 길이);
for (let i = 0; i < len; i++) {
  newRow[(R % len) + i] = row[i];
}

또한 R % (1차원 배열의 길이) + i이 배열의 길이를 초과했을 때를 고려하여, R % (1차원 배열의 길이) + i이 배열의 길이보다 클 경우에는 아래와 같은 공식을 사용한다.

newRow[(R % len) + i - len] = row[i];

따라서 아래와 같이 코드를 수정해준다.

const len = (1차원 배열의 길이);
for (let i = 0; i < len; i++) {
  if ((R % len) + i >= len) {
    newRow[(R % len) + i - len] = row[i];
  } else {
    newRow[(R % len) + i] = row[i];
  }
}

이 코드가 완료되면 1차원 배열이 R칸 회전한 것과 같은 배열이 만들어진다.

그리고 회전한 1차원 배열을 다시 2차원 배열의 형태로 만들어주면 모든 배열이 R번 회전한 효과를 낼 수 있다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M, R] = input[0].split(' ').map(Number);
const arr = input.slice(1).map((e) => e.split(' ').map(Number));
const answerArr = Array.from({ length: N }, () => Array(M).fill(0));
let [n, m] = [N, M];

function makeArr(lt, rb) {
    const row = [];
    // 하
    for (let i = lt[0]; i < rb[0]; i++) {
        row.push(arr[i][lt[1]]);
    }
    // 우
    for (let i = lt[1]; i < rb[1]; i++) {
        row.push(arr[rb[0]][i]);
    }
    // 상
    for (let i = rb[0]; i > lt[0]; i--) {
        row.push(arr[i][rb[1]]);
    }
    // 좌
    for (let i = rb[1]; i > lt[1]; i--) {
        row.push(arr[lt[0]][i]);
    }
    if (row.length === 0) row.push(arr[lt[0]][lt[1]]);

    return row;
}

function getRowAfterRotate(row, len) {
    const newRow = Array(len).fill(0);
    for (let i = 0; i < len; i++) {
        if ((R % len) + i >= len) {
            newRow[(R % len) + i - len] = row[i];
        } else {
            newRow[(R % len) + i] = row[i];
        }
    }
    return newRow;
}

function getArrAfterRotate(row, lt, rb) {
    let count = 0;
    // 하
    for (let i = lt[0]; i < rb[0]; i++) {
        answerArr[i][lt[1]] = row[count++];
    }
    // 우
    for (let i = lt[1]; i < rb[1]; i++) {
        answerArr[rb[0]][i] = row[count++];
    }
    // 상
    for (let i = rb[0]; i > lt[0]; i--) {
        answerArr[i][rb[1]] = row[count++];
    }
    // 좌
    for (let i = rb[1]; i > lt[1]; i--) {
        answerArr[lt[0]][i] = row[count++];
    }
}

let count = 0;
while (n > 0 && m > 0) {
    // 왼쪽 위 좌표
    const lt = [count, count];
    // 오른쪽 아래 좌표
    const rb = [N - 1 - count, M - 1 - count];
    // 외곽을 감싼 배열을 1차원 배열로 변환
    const row = makeArr(lt, rb);
    // 1차원 배열에 회전 적용시키기
    const newRow = getRowAfterRotate(row, row.length);
    // 1차원 배열을 2차원 배열로 만들기
    getArrAfterRotate(newRow, lt, rb);

    n -= 2;
    m -= 2;
    count++;
}

let answer = '';
for (let i = 0; i < answerArr.length; i++) {
    answer += answerArr[i].join(' ') + '\n';
}
console.log(answer.trimEnd());