17276번 - 배열 돌리기

1️⃣ 모듈러 연산

 

✏️ 풀이 과정

경우의 수가 8가지 뿐이므로 노가다를 하면 간단하게 해결할 수 있지만 귀찮아서 한 번에 쓰려 한다면 골치아파지는 문제입니다. 기본적인 아이디어는 사방탐색을 하듯이 8개의 축선의 값을 따로 저장해서 n의 크기와 회전 각도에 따라 새롭게 바뀐 위치에 덮어쓰는 것입니다. 축선의 좌표는 ir, ic, dr, dc 네 개의 상수 배열을 이용해 저장해서 크기 n에 따라 탐색합니다.

 

여기서 각도를 어떻게 8가지 경우의 수에 적절히 매칭하는 지가 관건인데 여기서는 각도의 원리를 이용해서 각도가 음수일 경우 360도를 더해서 양수를 만드는 방법을 이용했습니다.(삼각함수를 배워본 적이 있다면 어떤 공식인지 아실 것입니다. 잘 모른다 하더라도 360도를 더하면 제 자리이기 때문에 시계 방향으로 돌았을 때의 같은 위치에 오게 된다고 생각하면 됩니다.) 각도 또한 45도 간격으로 8가지가 존재(9가지이지만 0과 360이 같음)하기 때문에 모듈러 연산으로 각도를 45로 나누고 8에 대해 모듈러 연산을 진행하면 0부터 7까지의 인덱스로 변환할 수 있습니다.

 

이런 점을 이용해서 축선을 왼쪽부터 4개 저장하고 가장 왼쪽 위에서 시작한 축선이 어디로 이동하는 지를 기점으로 45도 간격으로 4개를 덮어쓰면 됩니다. 가령 180도를 이동했을 때는 (n-1, n-1)지점에서부터 왼쪽 위로 올라가면서 배열에 첫 번째 축선의 내용을 덮어씁니다.

 

지점 4개를 잡으면 나머지 시작점은(앞선 4개의 끝점이기 때문에) 신경 쓸 필요가 없기 때문에 문제 풀이가 끝납니다.

 

덮어 쓴 배열을 출력하면 문제 해결 완료입니다.

 

⏱ 시간 복잡도

이차원 배열 전체를 덮어쓰거나 출력하는 연산 이외의 것을 하지 않기 때문에 시간 복잡도는 O(n^2)이 됩니다. n이 500까지 가능하기 때문에 250000 * 10 = 2500000으로 주어진 시간 내에 해결이 가능한 것을 예측할 수 있습니다.

 

💻 코드

JavaScript

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

const T = Number(input[0]);
let n,
    d,
    idx = 1;

// 축선 탐색을 위한 상수 배열
const dr = [1, 1, 1, 0, -1, -1, -1, 0];
const dc = [1, 0, -1, -1, -1, 0, 1, 1];

for (let t = 0; t < T; t++) {
    [n, d] = input[idx++].split(" ").map(Number);
    // 각도를 모두 양수로 변경
    if (d < 0) {
        d += 360;
    }
    const arr = Array.from(Array(n), () => input[idx++].split(" "));
    // 축선 탐색을 위한 상수 배열(시작 위치)
    const ir = [0, 0, 0, parseInt(n / 2), n - 1, n - 1, n - 1, parseInt(n / 2)];
    const ic = [0, parseInt(n / 2), n - 1, n - 1, n - 1, parseInt(n / 2), 0, 0];
    const lines = Array.from(Array(4), () => Array(n));

    // 축선을 따로 저장(4개 저장하면 반대 방향은 필요 X)
    for (let i = 0; i < 4; i++) {
        for (let j = 0; j < n; j++) {
            lines[i][j] = arr[ir[i] + dr[i] * j][ic[i] + dc[i] * j];
        }
    }

    // 회전시킨 위치에 축선을 덮어쓴다.(시작 위치에서 n칸)
    for (let i = 0; i < 4; i++) {
        // 모듈러 연산으로 이동 위치 계산 인덱스 생성
        let idx = (d / 45 + i) % 8;
        // 저장한 축선 4개에 해당하는 위치를 덮어쓴다.
        for (let j = 0; j < n; j++) {
            arr[ir[idx] + dr[idx] * j][ic[idx] + dc[idx] * j] = lines[i][j];
        }
    }
    // 결과를 출력
    console.log(arr.map((row) => row.join(" ")).join("\n"));
}