[JAVA] 백준 16926번 배열 돌리기 1 자바 풀이

in STUDY / PS

단순 구현 문제입니다.

📚 문제

🔗 문제 링크

백준 16926번: 배열 돌리기 1

📖 문제 설명

  • N×M 크기의 배열이 있을 때, 배열을 반시계 방향으로 R번 회전시키려고 함
  • 배열의 가장 바깥쪽 테두리부터 안쪽까지 하나씩 회전해야 함

🔍 입력 조건

  • 첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어짐
  • 둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어짐

🔍 출력 조건

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

🧩 문제 분류

  • 알고리즘: 구현, 시뮬레이션
  • 자료구조: 2차원 배열
  • 난이도: GOLD V

🚀 접근 방법

  1. 배열을 테두리 단위로 나누어 회전
  2. 각 테두리를 실제 회전 횟수만큼 반시계방향으로 회전
  3. 실제 회전 횟수는 R을 테두리의 둘레로 나눈 나머지

💻 구현

/**
 * BAEKJOON ONLINE JUDGE
 * 문제 이름 : 배열 돌리기 1
 * 문제 번호 : 16926
 * 난이도 : GOLD V
 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// N과 M 둘 중 하나는 짝수임
public class Main {
    static int N, M, R;
    static int[][] arr;

    public static void rotate(){
        int cycle = Math.min(N, M) / 2;

        for (int i = 0; i < cycle; i++){
            int rowLen = N - 2 * i - 1;
            int colLen = M - 2 * i - 1;
            int total = 2 * (rowLen + colLen);

            // R이 커질 수 있으므로, total로 나눈 나머지만큼만 돌리면 됨.
            int actualRotate = R % total;

            for (int j = 0; j < actualRotate; j++){
                int temp = arr[i][i];

                // 위쪽
                for (int k = i; k < M - 1 - i; k++){
                    arr[i][k] = arr[i][k+1];
                }

                // 오른쪽
                for (int k = i ; k < N - 1 - i; k++){
                    arr[k][M-1-i] = arr[k+1][M-1-i];
                }

                // 아래쪽
                for (int k = M-1-i; k > i; k--){
                    arr[N-1-i][k] = arr[N-1-i][k-1];
                }

                // 왼쪽
                for (int k = N-1-i; k > i; k--){
                    arr[k][i] = arr[k-1][i];
                }

                arr[i + 1][i] = temp;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        arr = new int[N][M];
        for (int i = 0;  i < N; i++){
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < M; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        rotate();

        for (int i = 0; i < N; i++){
            for (int j = 0; j < M; j++){
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
}

⏱ 시간 복잡도

  • O(N×M×R): 각 테두리마다 R번의 회전을 수행
  • 하지만 실제로는 R % (테두리 길이)만큼만 회전하므로 더 효율적

💾 공간 복잡도

  • O(N×M): 원본 배열 외에 추가 공간이 거의 필요하지 않음

📝 회고

  • 배열 cycle을 설정하고, 그 값으로 정형화시키는게 어려웠다.
  • temp로 정한 값을 기준으로, 자신만의 순서를 정해서 이동하는 게 좋을듯
  • 배열을 시계방향으로 탐색하면서 배열을 이동시켜야 잘 이동됨.
  • temp 배열을 사용하면 상관없을 지도