(C++,Java) [백준 16935번] 배열 돌리기 3

문제 링크

배열 돌리기 3

설명

N*M 크기의 배열을 다음 6가지 방법으로 돌리는 문제
1. 배열 상하 뒤집기
2. 배열 좌우 뒤집기
3. 배열 오른쪽 90도 회전
4. 배열 왼쪽 90도 회전
5. 배열 4분할 후 각각을 오른쪽 90도 회전
6. 배열 4분할 후 각각을 왼쪽 90도 회전

접근

• 제한은 다음과 같음
  2 ≤ N, M ≤ 100
  1 ≤ R ≤ 1,000
  N, M은 짝수
  1 ≤ datas[i][j] <= 10^8
• 가장 나이브한 접근 방법으로 모든 원소를 임시 배열을 생성한 후 다시 원본 배열로 돌리는 방법이 있는데, 이 방법을 사용했을 때의 시간 복잡도는 O(2*NMR)이고, N,M,R은 각각 10^2, 10^2, 10^3이므로 충분히 가능하다고 판단했다.
• 다만 n,m,i,j중 어떤 변수를 행, 열로 잡아야 하는가에 대한 어려움이 있었는데, 친구가 알려준 방법을 통해 해결했다. 어차피 NM 모두 작으므로 *매번 새 배열을 깊은 복사를 통해 행과 열을 새로 받아온 다음 r,c에 저장해서 해결했다.**

풀이

• 1번은 for i = 0 to (r/2) 하나로 해결할 수 있다.
  C++의 경우 행 우선이므로 i번 행과 i-r-1번 행을 swap하면 된다.
• 2번은 열을 바꾸는 연산이므로, 열 개수만큼 돌면서 해당 열에서 행의 원소들을 swap하면 된다.
• 3번은 계산해보면 i번 행, j번 열의 원소들이 j번 행의 i-r-1번 열로 가는 연산이므로 임시 배열을 만들어서 옮긴 다음 해당 배열을 원본 배열에 옮기면 된다.
• 4번은 i번 행, j번 열의 원소들이 c-j-1번 행의 i번 열로 가는 연산이므로 계산한 뒤 3번과 같이 옮기면 된다.
• 5,6번은 우선 4개의 배열로 쪼개야 하는데, 각각의 배열은 (0,0)을 왼쪽 위라고 생각했을 때 다음과 같다.
  • 이후 5번의 경우 1 = 4, 4 = 3, 3 = 2, 2 = 1
  • 6번의 경우 1 = 2, 2 = 3, 3 = 4, 4 = 1 순서로 값을 넣어준 후 원본에 옮기면 된다.
    사실 왼쪽으로 90도 회전은 오른쪽으로 90도 회전을 3번 한 것과 똑같은 효과라서, 귀찮으면 3,5번만 구현해놓고 4,6번은 3,5번을 3번 돌려도 통과되긴 하더라.
• 1번 배열: (0 to r/2), (0 to c/2)
  2번 배열: (0 to r/2), (c/2 to c)
  3번 배열: (r/2 to r), (c/2 to c)
  4번 배열: (r/2 to r), (0 to c/2)

코드(C++)

#include <vector>
#include <iostream>
using namespace std;
vector<vector<int>> originals;
constexpr int MAX = 102;
int temps[MAX][MAX];
int r, n, m, x;
void input() {
    cin >> n >> m >> r;

        for (int i = 0; i < n; i++) {
            originals.push_back(vector<int>(m));

            for (int j = 0; j < m; j++) {
                cin >> originals[i][j];
            }
        }


}
vector<vector<int>> rotate(int op,vector<vector<int>> board) {
    int index = 0;
    int r, c;
    r = board.size();
    c = board[0].size();
    if (op == 1) {
        for (int i = 0; i < r / 2; i++) {
            for (int j = 0; j < c; j++) {
                swap(board[i][j], board[r-i-1][j]);
            }
        }
    }

    else if (op == 2) {
        for (int i = 0; i < c / 2; i++) {
            for (int j = 0; j < r; j++) {
                swap(board[j][i], board[j][c - i - 1]);
            }
        }
    }
    else if (op == 3) {

        vector<vector<int>> temp(c);
        for (int i = 0; i < c; i++)
            temp[i].resize(r);


            for (int i = 0; i <r; i++) {

                for (int j = 0; j < c; j++) {
                    temp[j][r - i - 1] = board[i][j];
                }
            }

            board.resize(c);
            for (int i = 0; i < c; i++)
                board[i].resize(r);

            for (int i = 0; i < c; i++) {
                for (int j = 0; j < r; j++) {
                    board[i][j] = temp[i][j];
                }
            }


    }
    else if (op == 4) {

            vector<vector<int>> temp(c);
            for (int i = 0; i < c; i++)
                temp[i].resize(r);

            for (int i = 0; i <r; i++) {
                for (int j = 0; j < c; j++) {
                    temp[c - j - 1][i] = board[i][j];
                }
            }

            board.resize(c);
            for (int i = 0; i < c; i++)
                board[i].resize(r);
            for (int i = 0; i < c; i++) {
                for (int j = 0; j < r; j++) {
                    board[i][j] = temp[i][j];
                }
            }

    }
    else if (op == 5) {
        int cn, cm;
        vector<vector<int>> temp(r);
            for (int i = 0; i <r; i++)
                temp[i].resize(c);
            cn = r / 2;
            cm = c / 2;
            // 1
            for (int i = 0; i < cn; i++) {
                for (int j = 0; j < cm; j++) {
                    int nx = i + cn;
                    int ny = j;
                    temp[i][j] = board[nx][ny];
                }
            }

            // 2
            for (int i = 0; i < cn; i++) {
                for (int j = cm; j < c; j++) {
                    int nx = i;
                    int ny = j - cm;
                    temp[i][j] = board[nx][ny];
                }
            }
            // 3
            for (int i = cn; i <r; i++) {
                for (int j = cm; j < c; j++) {
                    int nx = i - cn;
                    int ny = j;
                    temp[i][j] = board[nx][ny];
                }
            }
            // 4

            for (int i = cn; i <r; i++) {
                for (int j = 0; j < cm; j++) {
                    int nx = i;
                    int ny = j + cm;
                    temp[i][j] = board[nx][ny];
                }
            }

            for (int i = 0; i <r; i++) {
                for (int j = 0; j < c; j++) {
                    board[i][j] = temp[i][j];
                }
            }



    }
    else if (op == 6) {

        int cn, cm;
        vector<vector<int>> temp(r);
        for (int i = 0; i < r; i++)
            temp[i].resize(c);
        cn = r / 2;
        cm = c / 2;
        // 1
        for (int i = 0; i < cn; i++) {
            for (int j = 0; j < cm; j++) {
                int nx = i;
                int ny = j + cm;
                temp[i][j] = board[nx][ny];
            }
        }

        // 2
        for (int i = 0; i < cn; i++) {
            for (int j = cm; j < c; j++) {
                int nx = i + cn;
                int ny = j;
                temp[i][j] = board[nx][ny];
            }
        }

        // 3
        for (int i = cn; i < r; i++) {
            for (int j = cm; j < c; j++) {
                int nx = i;
                int ny = j - cm;
                temp[i][j] = board[nx][ny];
            }
        }
        // 4

        for (int i = cn; i < r; i++) {
            for (int j = 0; j < cm; j++) {
                int nx = i - cn;
                int ny = j;
                temp[i][j] = board[nx][ny];
            }
        }

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                board[i][j] = temp[i][j];
            }
        }


    }
    return board;
}
int main() {
    cin.tie(0); ios::sync_with_stdio(0);
    input();
    vector<vector<int>> board = originals;
    for (int cnt = 0; cnt < r; cnt++) {
        int op;
        cin >> op;

        board = rotate(op, board);



    }

    for (auto i : board) {
        for (auto j : i)
            cout << j << ' ';
        cout << "\n";
    }

}

코드(JAVA)

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int temp[][],originals[][];
    public static String solve() throws IOException {

        int r, n, m, x;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        originals = new int[n][m];
        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<m; j++) {
                originals[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int[][] board = originals;
        st = new StringTokenizer(br.readLine());
        while(st.hasMoreTokens()) {
            int op = Integer.parseInt(st.nextToken());
            board = rotate(op, board);
        }
        for (int[] is : board) {
            for (int is2 : is) {
                sb.append(is2).append(" ");
            }
            sb.append("\n");
        }
        return sb.toString();
    }
    static int[][] rotate(int op,int[][] board) {
        int r, c;
        r = board.length;
        c = board[0].length;
        if (op == 1) {
            for (int i = 0; i < r / 2; i++) {
                for (int j = 0; j < c; j++) {
                    int t = board[i][j];
                    board[i][j] = board[r-i-1][j];
                    board[r-i-1][j] = t;
                }
            }
        }

        else if (op == 2) {
            for (int i = 0; i < c / 2; i++) {
                for (int j = 0; j < r; j++) {
                    int t = board[j][i];
                    board[j][i] = board[j][c-i-1];
                    board[j][c-i-1] = t;
                }
            }
        }
        else if (op == 3) {
            temp = new int[c][r];

                for (int i = 0; i <r; i++) {

                    for (int j = 0; j < c; j++) {
                        temp[j][r - i - 1] = board[i][j];
                    }
                }
            board = new int[c][r];
                for (int i = 0; i < c; i++) {
                    for (int j = 0; j < r; j++) {
                        board[i][j] = temp[i][j];
                    }
                }


        }
        else if (op == 4) {

            temp = new int[c][r];
                for (int i = 0; i <r; i++) {
                    for (int j = 0; j < c; j++) {
                        temp[c - j - 1][i] = board[i][j];
                    }
                }

                board = new int[c][r];
                for (int i = 0; i < c; i++) {
                    for (int j = 0; j < r; j++) {
                        board[i][j] = temp[i][j];
                    }
                }

        }
        else if (op == 5) {
            int cn, cm;
            temp = new int [r][c];
                cn = r / 2;
                cm = c / 2;
                // 1
                for (int i = 0; i < cn; i++) {
                    for (int j = 0; j < cm; j++) {
                        int nx = i + cn;
                        int ny = j;
                        temp[i][j] = board[nx][ny];
                    }
                }

                // 2
                for (int i = 0; i < cn; i++) {
                    for (int j = cm; j < c; j++) {
                        int nx = i;
                        int ny = j - cm;
                        temp[i][j] = board[nx][ny];
                    }
                }
                // 3
                for (int i = cn; i <r; i++) {
                    for (int j = cm; j < c; j++) {
                        int nx = i - cn;
                        int ny = j;
                        temp[i][j] = board[nx][ny];
                    }
                }
                // 4

                for (int i = cn; i <r; i++) {
                    for (int j = 0; j < cm; j++) {
                        int nx = i;
                        int ny = j + cm;
                        temp[i][j] = board[nx][ny];
                    }
                }

                for (int i = 0; i <r; i++) {
                    for (int j = 0; j < c; j++) {
                        board[i][j] = temp[i][j];
                    }
                }



        }
        else if (op == 6) {

            int cn, cm;
            temp = new int [r][c];
            cn = r / 2;
            cm = c / 2;
            // 1
            for (int i = 0; i < cn; i++) {
                for (int j = 0; j < cm; j++) {
                    int nx = i;
                    int ny = j + cm;
                    temp[i][j] = board[nx][ny];
                }
            }

            // 2
            for (int i = 0; i < cn; i++) {
                for (int j = cm; j < c; j++) {
                    int nx = i + cn;
                    int ny = j;
                    temp[i][j] = board[nx][ny];
                }
            }

            // 3
            for (int i = cn; i < r; i++) {
                for (int j = cm; j < c; j++) {
                    int nx = i;
                    int ny = j - cm;
                    temp[i][j] = board[nx][ny];
                }
            }
            // 4

            for (int i = cn; i < r; i++) {
                for (int j = 0; j < cm; j++) {
                    int nx = i - cn;
                    int ny = j;
                    temp[i][j] = board[nx][ny];
                }
            }

            for (int i = 0; i < r; i++) {
                for (int j = 0; j < c; j++) {
                    board[i][j] = temp[i][j];
                }
            }


        }
        return board;    
    }
    public static void main(String[] args) throws IOException {
        System.out.println(solve());
    }
}