16926 배열 돌리기 1 (자바스크립트)

문제

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.

A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5]
   ↓                                       ↑
A[2][1]   A[2][2] ← A[2][3] ← A[2][4]   A[2][5]
   ↓         ↓                   ↑         ↑
A[3][1]   A[3][2] → A[3][3] → A[3][4]   A[3][5]
   ↓                                       ↑
A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5]

예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.

1 2 3 4       2 3 4 8       3 4 8 6
5 6 7 8       1 7 7 6       2 7 8 2
9 8 7 6   →   5 6 8 2   →   1 7 6 3
5 4 3 2       9 5 4 3       5 9 5 4
 <시작>         <회전1>        <회전2>

배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.

입력

첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

출력

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

=====

문제 분석

2차원 배열을 겉에서부터 시작하여 시계방향으로 움직이면서 좌표와 그 안에 적힌 숫자 값을 좌표 객체와 값 객체에 담아줄 것이다.

let stage = 0;
const coordinates = {};
const values = {};
const answer = Array.from({ length: n }, () =>
    Array.from({ length: m }, () => -1)
);

좌표 객체에 stage:  (0,0)~(0,m-1), (1,m-1)~(n-2,m-1), (n-1, m-1)~(n-1,0) , (n-2,0)~(1,0)

이것을 stage와 엮어서 시작 끝값을 점화식으로 만들면 아래와 같다.

row의 시작 값 rs, row의 끝값 re

let [rs, re] = [0 + stage, n - 1 - stage];
let [cs, ce] = [0 + stage, m - 1 - stage];

반복문을 계속 적으로 돌다가 rs,cs가 re,ce를 역전하면 종료할 것이다.

while (true) {
        const coordinate = [];
        const value = [];
        let [rs, re] = [0 + stage, n - 1 - stage];
        let [cs, ce] = [0 + stage, m - 1 - stage];
        if (rs > re || cs > ce) break;
        for (let c = cs; c <= ce; c++) {
            coordinate.push([rs, c]);
            value.push(gr[rs][c]);
        }
        for (let r = rs + 1; r <= re - 1; r++) {
            coordinate.push([r, ce]);
            value.push(gr[r][ce]);
        }
        for (let c = ce; c >= cs; c--) {
            coordinate.push([re, c]);
            value.push(gr[re][c]);
        }
        for (let r = re - 1; r >= rs + 1; r--) {
            coordinate.push([r, cs]);
            value.push(gr[r][cs]);
        }
        if (coordinate.length === 0) {
            break;
        }
        coordinates[stage] = coordinate;
        values[stage] = value;
        stage++;
}

이제 values에 적혀 있는 것들을 각각 t만큼 shift와 push를 반복해준 뒤 해당하는 좌표에 값을 넣어준 뒤 출력하면 된다.

for (let i = 0; i < stage; i++) {
        for (let j = 0; j < t; j++) {
            const t = values[i].shift();
            values[i].push(t);
        }
        for (let k = 0; k < values[i].length; k++) {
            const [x, y] = coordinates[i][k];
            answer[x][y] = values[i][k];
        }
    }
console.log(answer.map((v) => v.join(' ')).join('\n'));

참고로 나머지 연산을 통해서 values를 처리한다면 더 최적화 될 것이다.

 

정답 코드

const main = (n, m, t, gr) => {
    let stage = 0;
    const coordinates = {};
    const values = {};
    const answer = Array.from({ length: n }, () =>
        Array.from({ length: m }, () => -1)
    );

    while (true) {
        const coordinate = [];
        const value = [];
        let [rs, re] = [0 + stage, n - 1 - stage];
        let [cs, ce] = [0 + stage, m - 1 - stage];
        if (rs > re || cs > ce) break;
        for (let c = cs; c <= ce; c++) {
            coordinate.push([rs, c]);
            value.push(gr[rs][c]);
        }
        for (let r = rs + 1; r <= re - 1; r++) {
            coordinate.push([r, ce]);
            value.push(gr[r][ce]);
        }
        for (let c = ce; c >= cs; c--) {
            coordinate.push([re, c]);
            value.push(gr[re][c]);
        }
        for (let r = re - 1; r >= rs + 1; r--) {
            coordinate.push([r, cs]);
            value.push(gr[r][cs]);
        }
        if (coordinate.length === 0) {
            break;
        }
        coordinates[stage] = coordinate;
        values[stage] = value;
        stage++;
    }
    for (let i = 0; i < stage; i++) {
        for (let j = 0; j < t; j++) {
            const t = values[i].shift();
            values[i].push(t);
        }
        for (let k = 0; k < values[i].length; k++) {
            const [x, y] = coordinates[i][k];
            answer[x][y] = values[i][k];
        }
    }
    console.log(answer.map((v) => v.join(' ')).join('\n'));
};

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, m, t] = input[0].split(' ').map((v) => +v);
const gr = input.slice(1).map((v) => v.split(' ').map((v) => +v));
main(n, m, t, gr);