[BOJ/Java] 16935. 배열 돌리기 3

[BOJ/Java] 16935. 배열 돌리기 3

16935번: 배열 돌리기 3

---

문제 해석

이 문제는 2차원 배열에 대해 여러 가지 연산을 수행하고 최종 결과를 출력하는 문제다. 주어진 연산은 총 6가지이며, 배열의 상하 반전, 좌우 반전, 오른쪽 90도 회전, 왼쪽 90도 회전, 그리고 블록을 이동시키는 특수한 연산 두 가지를 포함한다. 각 연산을 정확히 수행한 후 결과를 출력해야 한다.

풀이 과정

1. 입력 받기: Java의 BufferedReader와 StringTokenizer를 사용하여 효율적으로 입력을 받는다. 이때, 배열의 크기, 연산의 개수, 그리고 각 연산들이 어떤 순서로 주어지는지를 입력받는다.
2. 연산 준비: ArrayDeque를 사용하여 입력된 연산을 큐에 저장한다. 이후 연산을 하나씩 꺼내면서 해당 연산을 수행한다.
3. 연산 최적화: 연속된 특정 연산들은 결과에 영향을 주지 않는 경우가 있다. 예를 들어, 상하 반전을 연속으로 두 번 수행하는 것은 원래 상태와 같으므로 이런 연산은 스킵한다.
4. 각 연산 수행: 각 연산에 맞는 메소드를 호출하여 배열을 조작한다. 메소드 내부에서는 주어진 연산의 특성에 맞게 배열 인덱스를 조정하고 결과를 임시 배열에 저장한 후, 원본 배열로 복사한다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().io();
    }

    private int[][] graph; // 주 배열
    private int[][] tmp; // 연산 결과를 임시로 저장할 배열
    private int n; // 배열의 행 수
    private int m; // 배열의 열 수
    private int r; // 수행할 연산의 수
    ArrayDeque<Integer> dq; // 연산을 저장할 덱

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());

        graph = new int[n][m];
        tmp = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dq = new ArrayDeque<Integer>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < r; i++) {
            dq.offer(Integer.parseInt(st.nextToken()));
        }

        sol();

        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph[0].length; j++) {
                sb.append(graph[i][j]).append(" ");
            }
            sb.append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void sol() {
        // 연산을 수행하는 메인 로직
        while (!dq.isEmpty()) {
            int c = dq.poll();

            if (!dq.isEmpty()) {
                // 연산 최적화: 연속된 연산이 결과에 영향을 미치지 않는 경우 스킵
                if (dq.peek() == c) {
                    if (c == 1 || c == 2) {
                        dq.poll();
                        continue;
                    }
                }

                if (c == 3 && dq.peek() == 4) {
                    dq.poll();
                    continue;
                }
                if (c == 4 && dq.peek() == 3) {
                    dq.poll();
                    continue;
                }

                if (c == 5 && dq.peek() == 6) {
                    dq.pop();
                    continue;
                }
                if (c == 6 && dq.peek() == 5) {
                    dq.pop();
                    continue;
                }
            }

            checkCalculation(c);
        }
    }

    private void checkCalculation(int c) {
        // 연산 번호에 따라 해당 연산을 수행
        switch (c) {
        case 1:
            calculation01(); // 상하 반전
            break;
        case 2:
            calculation02(); // 좌우 반전
            break;
        case 3:
            calculation03(); // 오른쪽 90도 회전
            break;
        case 4:
            calculation04(); // 왼쪽 90도 회전
            break;
        case 5:
            calculation05(); // 1번 그룹을 2번 위치로, 2번을 3번으로, 3번을 4번으로, 4번을 1번으로 이동
            break;
        case 6:
            calculation06(); // 1번 그룹을 4번 위치로, 4번을 3번으로, 3번을 2번으로, 2번을 1번으로 이동
            break;
        }
    }

    private void copy() {
        // 임시 배열의 내용을 주 배열로 복사
        graph = Arrays.copyOf(tmp, tmp.length);
        for (int i = 0; i < tmp.length; i++) {
            graph[i] = tmp[i].clone();
        }
    }

    	private void calculation01() {
		for (int i = graph.length - 1; i >= 0; i--) {
			tmp[i] = graph[graph.length - 1 - i].clone();
		}
		copy();
	}

	private void calculation02() {
		for (int i = 0; i < graph.length; i++) {
			for (int j = 0; j < graph[i].length; j++) {
				tmp[i][graph[i].length - 1 - j] = graph[i][j];
			}
		}
		copy();
	}

	private void calculation03() {
		tmp = new int[graph[0].length][graph.length];

		for (int i = 0; i < graph.length; i++) {
			int[] row = graph[i].clone();

			for (int j = 0; j < graph[0].length; j++) {
				tmp[j][graph.length - 1 - i] = row[j];
			}
		}
		copy();
	}

	private void calculation04() {
		tmp = new int[graph[0].length][graph.length];

		for (int i = 0; i < graph.length; i++) {
			int[] row = graph[i].clone();

			for (int j = 0; j < graph[0].length; j++) {
				tmp[graph[0].length - 1 - j][i] = row[j];
			}
		}
		copy();
	}

	private void calculation05() {
		// 1번 그룹 오른쪽 이동
		for (int i = 0; i < graph.length / 2; i++) {
			for (int j = 0; j < graph[0].length / 2; j++) {
				tmp[i][j + graph[0].length / 2] = graph[i][j];
			}
		}

		// 2번 그룹 아래쪽 이동
		for (int i = 0; i < graph.length / 2; i++) {
			for (int j = graph[0].length / 2 - 1; j < graph[0].length; j++) {
				tmp[i + graph.length / 2][j] = graph[i][j];
			}
		}

		// 3번 그룹 왼쪽 이동
		for (int i = graph.length / 2 - 1; i < graph.length; i++) {
			int c = graph[0].length / 2;
			for (int j = graph[0].length / 2 - 1; j >= 0; j--) {
				tmp[i][graph[0].length / 2 - 1 - j] = graph[i][c];
				c++;
			}
		}

		// 4번 그룹 위쪽 이동
		int r = graph.length - 1;
		for (int i = graph.length / 2 - 1; i >= 0; i--) {
			for (int j = 0; j < graph[0].length / 2; j++) {
				tmp[i][j] = graph[r][j];
			}
			r--;
		}

		copy();
	}

	private void calculation06() {
		// 1번 그룹 오른쪽 이동
		for (int i = 0; i < graph.length / 2; i++) {
			for (int j = 0; j < graph[0].length / 2; j++) {
				tmp[graph.length / 2 + i][j] = graph[i][j];
			}
		}

		// 2번 그룹 아래쪽 이동
		for (int i = graph.length / 2; i < graph.length; i++) {
			for (int j = 0; j < graph[0].length / 2; j++) {
				tmp[i][j + graph[0].length / 2] = graph[i][j];
			}
		}

		// 3번 그룹 왼쪽 이동
		for (int i = graph.length / 2; i < graph.length; i++) {
			for (int j = graph[0].length / 2; j < graph[0].length; j++) {
				tmp[i - graph.length / 2][j] = graph[i][j];
			}
		}

		// 4번 그룹 위쪽 이동
		for (int i = 0; i < graph.length / 2; i++) {
			for (int j = graph[0].length / 2; j < graph[0].length; j++) {
				tmp[i][j - graph[0].length / 2] = graph[i][j];
			}
		}

		copy();
	}
}

시간 복잡도 분석

각 연산은 배열의 모든 원소에 접근할 수 있어야 하므로 최소 O(NM)의 시간 복잡도를 가진다. 연산을 R번 수행하므로 최악의 경우 시간 복잡도는 O(RNM)이 된다. 하지만 연산 최적화를 통해 불필요한 연산을 줄이면 실제 실행 시간은 단축될 수 있다.

느낀점

이 문제를 통해 다양한 배열 조작 기법과 최적화 전략을 실습할 수 있었다. 특히, 연산을 최적화하여 불필요한 계산을 줄이는 부분이 흥미로웠으며, 이러한 접근 방식이 실제 애플리케이션에서의 성능 향상에 도움이 될 것으로 생각된다.