KimMinJun
Coding Note
KimMinJun
전체 방문자
오늘
어제
  • 분류 전체보기 (508) N
    • CS (1)
    • Web (29)
      • Vanilla JS (13)
      • TS (2)
      • React (7)
      • Next.js (5)
      • ETC (1)
    • Docker (14)
    • Git (5)
    • ALGORITHM (11)
      • 정렬 (6)
      • 최단경로 (1)
      • 자료구조 (1)
      • 슬라이딩 윈도우 (1)
      • etc (2)
    • PS (433) N
      • 백준 (187)
      • Programmers (106) N
      • CodeUp (21)
      • STL (3)
      • 제코베 JS 100제 (50)
      • SWEA (0)
      • LeetCode (65)
    • IT (1)
    • React 공식문서 (번역, 공부) (11)
      • Quick Start (2)
      • Installation (0)
      • Describing the UI (9)
      • Adding Interactivity (0)
      • Managing State (0)
      • Escape Hatches (0)
    • Next.js 공식문서 (번역, 공부) (3)
      • Getting Started (2)
      • Building Your Application (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 관리

공지사항

인기 글

태그

  • codeup
  • string
  • js
  • Level1
  • C
  • 다이나믹 프로그래밍
  • 그래프
  • C++
  • Level 0
  • 제코베 JS 100제
  • 백준
  • Level 2
  • Level 1
  • recursion
  • 정렬
  • LeetCode
  • 수학
  • 문자열
  • tree
  • programmers

최근 댓글

최근 글

hELLO · Designed By 정상우.
KimMinJun

Coding Note

PS/백준

백준 / 구현 / 16926번 / 배열 돌리기 1 / JS

2022. 6. 24. 10:00

문제

크기가 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 ≤ N, M ≤ 300
  • 1 ≤ R ≤ 1,000
  • min(N, M) mod 2 = 0
  • 1 ≤ Aij ≤ 108
/* 배열 돌리기 1 */
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
// const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');

// N = 행, M = 열, R = 회전 수
const [N, M, R] = input.shift().split(' ').map(Number);
let matrix = [];
input.map(item => {
  matrix.push(item.split(' ').map(Number));
});

function rotate(N, M, matrix) {
  const rect_cnt = Math.min(N, M) / 2;

  for(let cnt=0; cnt<rect_cnt; cnt++) {
    const row = N - cnt - 1;
    const col = M - cnt - 1;

    // 회전해야 하는 사각형의 기준점
    const tmp = matrix[cnt][cnt];

    // 위: 오른쪽에서 왼쪽으로
    for(let j=cnt; j<col; j++) {
      matrix[cnt][j] = matrix[cnt][j+1];
    }
    
    // 오른쪽: 아래에서 위로
    for(let i=cnt; i<row; i++) {
      matrix[i][col] = matrix[i+1][col];
    }

    // 아래: 왼쪽에서 오른쪽으로
    for(let j=col; j>cnt; j--) {
      matrix[row][j] = matrix[row][j-1];
    }

    // 왼쪽: 위에서 아래로
    for(let i=row; i>cnt; i--) {
      matrix[i][cnt] = matrix[i-1][cnt];
    }

    matrix[cnt+1][cnt] = tmp;
  }
}
function solution(N, M, R, matrix) {
  for(let i=0; i<R; i++) {
    rotate(N, M, matrix);
  }
  
  matrix.map(row => {
    console.log(row.join(' '));
  });
}

solution(N, M, R, matrix);

먼저 회전을 해야 하는 사각형의 갯수를 알아야 한다.

문제에서 제한에 보면

  • min(N, M) mod 2 = 0

이라는 항목이 있는데, 여기서 힌트를 얻었다.

 

min(N, M) / 2를 하면, 사각형의 갯수를 알 수 있다.

그리고 회전의 기준은 각 사각형의 왼쪽 위 꼭짓점을 기준으로 잡았다.

 

따라서 가장 바깥쪽의 기준점은 (0, 0)이라고 볼 수 있다.

그리고 만약 위의 예제에서 같이 그 안쪽에 사각형이 존재한다면 그 사각형의 기준점은 (1, 1)이 될 것이다.

따라서 (0, 0)에서 사각형의 갯수 만큼 사각형의 기준점은 행과 열 둘다 +1씩 증가한다는 것을 알 수 있다.

 

그리고 각 변 마다 이동을 구현해주면 된다.

 

저작자표시 (새창열림)

'PS > 백준' 카테고리의 다른 글

백준 / DP(Dynamic Programming) / 2156번 / 포도주 시식 / JS  (0) 2022.07.03
백준 / 기하학 / 2477번 / 참외밭 / JS  (0) 2022.06.26
백준 / 그리디 / 1449번 / 수리공 항승 / JS  (0) 2022.05.15
백준 / 그리디(Greedy) / 2217번 / 로프 / JS  (0) 2022.05.10
    'PS/백준' 카테고리의 다른 글
    • 백준 / DP(Dynamic Programming) / 2156번 / 포도주 시식 / JS
    • 백준 / 기하학 / 2477번 / 참외밭 / JS
    • 백준 / 그리디 / 1449번 / 수리공 항승 / JS
    • 백준 / 그리디(Greedy) / 2217번 / 로프 / JS
    KimMinJun
    KimMinJun

    티스토리툴바