출처: https://www.acmicpc.net/problem/17276
문제 설명
크기가 n * n인 2차원 정수 배열 X가 있다. (n은 홀수) X를 45도만큼 시계방향 또는 반시계방향으로 돌리는 문제이다. 이때, 네 가지 경우 모두 원소의 기존 순서는 유지 되어야 하고, 회전하지 않는 원소들의 위치는 변하지 않는다.
Input:
T | int : 테스트 케이스의 수 (1 <= T <= 10)
board | int[][] : n * n인 2차원 정수 배열 (1 <= n*n < 250000)
D | int : 회전할 각도, 45의 배수 (0 <= |d| <= 360)
tempBoard | int[][] : 회전시킨 배열을 담을 임시 2차원 배열
실수 목록
40분이나 걸렸다. 실수다.
내 코드
5000ms
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int T;
static int[][] board;
static int N, D;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
T = Integer.parseInt(br.readLine());
for (int tc = 0; tc < T; tc++) {
input();
solve();
}
}
private static void solve() {
int[][] tempBoard = new int[N][N];
for (int i = 0; i < N; i++) {
tempBoard[i] = board[i].clone();
}
if (D < 0)
D += 360;
for (int i = 0; i < D / 45; i++) {
// 주 대각선 -> 가운데 열
fromMainCrossToMediumCol(board, tempBoard);
// 가운데 열 -> 부 대각선
fromMediumColToSubCross(board, tempBoard);
// 부 대각선 -> 가운데 행
fromSubCrossToMediumRow(board, tempBoard);
// 가운데 행 -> 주 대각선
fromMediumRowToMainCross(board, tempBoard);
for (int j = 0; j < N; j++) {
board[j] = tempBoard[j].clone();
}
}
print();
}
private static void print() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
// 주 대각선 -> 가운데 열
private static void fromMainCrossToMediumCol(int[][] board, int[][] tempBoard) {
for (int i = 0; i < N; i++) {
for (int j = i; j <= i; j++) {
tempBoard[i][((N + 1) / 2) - 1] = board[i][j];
}
}
}
// 가운데 열 -> 부 대각선
private static void fromMediumColToSubCross(int[][] board, int[][] tempBoard) {
for (int i = 0; i < N; i++) {
for (int j = i; j <= i; j++) {
tempBoard[i][N - 1 - i] = board[i][((N + 1) / 2) - 1];
}
}
}
// 부 대각선 -> 가운데 행
private static void fromSubCrossToMediumRow(int[][] board, int[][] tempBoard) {
for (int i = 0; i < N; i++) {
for (int j = i; j <= i; j++) {
tempBoard[((N + 1) / 2) - 1][N - i - 1] = board[i][N - i - 1];
}
}
}
// 가운데 행 -> 주 대각선
private static void fromMediumRowToMainCross(int[][] board, int[][] tempBoard) {
for (int i = 0; i < N; i++) {
for (int j = i; j <= i; j++) {
tempBoard[N - i - 1][N - j - 1] = board[((N + 1) / 2) - 1][N - i - 1];
}
}
}
private static void input() throws IOException {
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
board = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
}
}
다른 접근 방법 배우기, 내 코드에 적용하기
다른 사람의 풀이를 보고 나서 ..... 오..... 이래서 다른 사람이 작성한 코드를 꼭 봐야한다는 것을 깨달았다. 나는 무작정 문제에서 시키는 대로 구현하기 바빴지만(아니 사실 문제를 더 복잡하게 푼 것 같다) , 조금만 생각을 더 했더라면 간단하게 풀 수 있었을 것 같은 아쉬움이 든다.
다른 사람 코드: 900ms
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int n, d;
static int[][] arr, copy;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
while(t-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
if(d < 0) {
d += 360;
}
d /= 45;
arr = new int[n][n];
copy = new int[n][n];
for(int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
copy[i][j] = arr[i][j];
}
}
while(d-- > 0) {
rotate();
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
sb.append(arr[i][j]).append(' ');
}
sb.append('\n');
}
}
System.out.print(sb);
}
private static void rotate() {
for(int i = 0; i < n ; i++){
copy[i][n/2] = arr[i][i];
copy[i][i] = arr[n/2][i];
copy[n/2][i] = arr[n-i-1][i];
copy[n-i-1][i] = arr[n-i-1][n/2];
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
arr[i][j] = copy[i][j];
}
}
}
}
리펙토링 후 내 코드: 804ms
코드를 리펙토링하면서 시간이 너무 많이 걸려서 무슨 일인가 했더니 System.out.print()의 시간이 너무 느렸다. StringBuilder를 사용하고 5000ms -> 800ms로 줄어들었다.......... BufferedReader나 StringTokenizer를 전역 변수로 선언하는 게 편하긴 한데 이렇게 쓰면 안된다고 했다!!
package algorithm.baekjoon.S2_17276_배열돌리기;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int T, N, D;
static int[][] board, tempBoard;
public static void main(String[] args) throws IOException {
// input
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
while (T-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
if (D < 0) {
D += 360;
}
D /= 45;
board = new int[N][N];
tempBoard = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
tempBoard[i][j] = board[i][j];
}
}
// solve
solve();
// print
print();
}
}
private static void solve() {
while (D-- > 0) {
rotate();
}
}
private static void rotate() {
for (int i = 0; i < N; i++) {
tempBoard[i][N / 2] = board[i][i];
tempBoard[i][N - i - 1] = board[i][N / 2];
tempBoard[N / 2][N - i - 1] = board[i][N - i - 1];
tempBoard[N - i - 1][N - i - 1] = board[N / 2][N - i - 1];
}
for (int i = 0; i < N; i++) {
board[i] = tempBoard[i].clone();
}
}
private static void print() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sb.append(board[i][j]).append(" ");
}
sb.append("\n");
}
System.out.print(sb);
}
}