[JAVA] 백준 16935번 배열 돌리기 3 자바 풀이

31 Oct 2024 in STUDY / PS

단순 구현 문제입니다.

📚 문제

🔗 문제 링크

백준 16935번: 배열 돌리기 3

📖 문제 설명

• N×M 크기의 배열이 있을 때, 배열에 연산을 R번 적용하려고 함
• 연산은 총 6가지가 있음:
  1. 상하 반전
  2. 좌우 반전
  3. 오른쪽 90도 회전
  4. 왼쪽 90도 회전
  5. 4개의 부분 배열로 나눠서 시계 방향 회전
  6. 4개의 부분 배열로 나눠서 반시계 방향 회전

🔍 입력 조건

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

🔍 출력 조건

• 입력으로 주어진 배열에 R개의 연산을 순서대로 수행한 결과를 출력

🧩 문제 분류

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

🚀 접근 방법

1. 각 연산을 별도의 메소드로 구현
2. 상하/좌우 반전은 간단히 변환
3. 90도 회전은 새로운 배열을 만들어 인덱스 매핑
4. 부분 배열 이동은 임시 배열을 사용하여 구현

💻 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M, R;
    static int[][] arr;

    private static void turn_array(int method) {
        switch (method){
            case 1:
                flip_vertical();
                break;
            case 2:
                flip_horizonal();
                break;
            case 3:
                rotate_90_right();
                break;
            case 4:
                rotate_90_left();
                break;
            case 5:
                part_move();
                break;
            case 6:
                part_move_reverse();
                break;
        }
    }

    // 상하 반전
    private static void flip_vertical() {
        int[][] temp = new int[N][M];

        for (int i = 0; i < N; i++){
            for (int j = 0; j < M; j++){
                temp[i][j] = arr[N-i-1][j];
            }
        }

        arr = temp;
    }

    // 좌우 반전
    private static void flip_horizonal() {
        int[][] temp = new int[N][M];

        for (int i = 0; i < N; i++){
            for (int j = 0; j < M; j++){
                temp[i][j] = arr[i][M-j-1];
            }
        }

        arr = temp;
    }

    // 시계방향 90도 회전
    private static void rotate_90_right() {
        int[][] temp = new int[M][N];

        for (int i = 0; i < M; i++){
            for (int j = 0; j < N; j++){
                temp[i][j] = arr[N-j-1][i];
            }
        }

        // N , M 이 바뀌는 점 명심!
        arr = temp;
        int num = N;
        N = M;
        M = num;
    }

    // 반시계방향 90도 회전
    private static void rotate_90_left() {
        int[][] temp = new int[M][N];

        for (int i = 0; i < M; i++){
            for (int j = 0; j < N; j++){
                temp[i][j] = arr[j][M-i-1];
            }
        }

        arr = temp;
        int num = N;
        N = M;
        M = num;
    }

    // 부분 변환
    private static void part_move() {
        int[][] temp = new int[N][M];

        int halfRow = N/2;
        int halfCol = M/2;

        // 1번 -> 2번 (왼쪽 위 -> 오른쪽 위)
        for(int i = 0; i < halfRow; i++) {
            for(int j = 0; j < halfCol; j++) {
                temp[i][j + halfCol] = arr[i][j];
            }
        }

        // 2번 -> 3번 (오른쪽 위 -> 오른쪽 아래)
        for(int i = 0; i < halfRow; i++) {
            for(int j = halfCol; j < M; j++) {
                temp[i + halfRow][j] = arr[i][j];
            }
        }

        // 3번 -> 4번 (오른쪽 아래 -> 왼쪽 아래)
        for(int i = halfRow; i < N; i++) {
            for(int j = halfCol; j < M; j++) {
                temp[i][j - halfCol] = arr[i][j];
            }
        }

        // 4번 -> 1번 (왼쪽 아래 -> 왼쪽 위)
        for(int i = halfRow; i < N; i++) {
            for(int j = 0; j < halfCol; j++) {
                temp[i - halfRow][j] = arr[i][j];
            }
        }

        // 임시 배열을 원본으로 복사
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                arr[i][j] = temp[i][j];
            }
        }
    }

    // 부분 변환 반대로
    private static void part_move_reverse() {
        int[][] temp = new int[N][M];  // 전체 크기의 임시 배열 사용

        int halfRow = N/2;
        int halfCol = M/2;

        // 1번 그룹 -> 4번 위치로
        for(int i = 0; i < halfRow; i++) {
            for(int j = 0; j < halfCol; j++) {
                temp[i + halfRow][j] = arr[i][j];
            }
        }

        // 4번 그룹 -> 3번 위치로
        for(int i = halfRow; i < N; i++) {
            for(int j = 0; j < halfCol; j++) {
                temp[i][j + halfCol] = arr[i][j];
            }
        }

        // 3번 그룹 -> 2번 위치로
        for(int i = halfRow; i < N; i++) {
            for(int j = halfCol; j < M; j++) {
                temp[i - halfRow][j] = arr[i][j];
            }
        }

        // 2번 그룹 -> 1번 위치로
        for(int i = 0; i < halfRow; i++) {
            for(int j = halfCol; j < M; j++) {
                temp[i][j - halfCol] = arr[i][j];
            }
        }

        // 임시 배열을 원본으로 복사
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                arr[i][j] = temp[i][j];
            }
        }
    }

    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());
            }
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < R; i++){
            int method = Integer.parseInt(st.nextToken());
            turn_array(method);
        }

        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번의 연산을 수행하므로 전체 시간복잡도는 O(R×N×M)

💾 공간 복잡도

• O(N×M): 원본 배열과 동일한 크기의 임시 배열이 필요

📝 회고

• 간단해 보이지만 모른채로 90도 회전을 구현해보면 생각보다 까다롭다.
• 삼성 코테 연습하며 배열 회전관련 구현에 많이 맞아보다 보니 중요성을 깨닫게 되었고..
• 계속해서 이런 단순 구현에 감을 유지하는 것이 좋을 것 같다.

📚 참고 자료