문제 바로가기

https://www.acmicpc.net/problem/16935

문제 소개 및 재정의

문제를 특별하게 해석할 필요가 없는 정직한 구현 문제다.

문제 패턴

주어진 방식대로 배열을 조작하는 문제이다.

어떻게 풀까? - 시뮬레이션

포인트

각 연산을 거치기 전 후의 셀의 좌표를 비교해서 맵핑하는 공식을 확보한다.
4번 연산은 3번연산을 3번 반복하는 식으로 간접적으로 구현 가능하다.
6번 연산은 5번연산을 3번 반복하는 식으로 간접적으로 구현 가능하다.

각 셀마다 최종위치를 계산해주고 해당 위치에 값을 저장하는 방식을 선택했다.
3,4번 연산은 행과 열의 길이를 서로 뒤바꾼다.
따라서 3,4번 연산할때마다 행과 열의 길이를 뒤바꾸고, 다른 셀을 선택해서 작업할때마다 행과 열의 길이를 원래대로 초기화해줘야 한다.

코드

import java.io.*;
import java.util.*;
public class Main {
	// 입력고정
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static StringBuilder output = new StringBuilder();
	
	// 세팅
	static int N;
	static int M;		// 원본 한셀에 대해 작업이 끝날때마다 초기화하는 용도
	static int workN; 	// 작업용. 3,4 명령마다 스왑하는 용도 
	static int workM;
	static int R;
	static int[][] origin;
	static int[][] answer;
	static int[] cmds;
	
	// 메소드
	static void reset() {
		workN=N;
		workM=M;
	}
	static void swap() { // 3,4 번 다음에 1,2,5,6 이 오면 N,M이 바뀐다. 그냥 한바닥 돌면서 하자.
		int tempN = workN;
		workN=workM;
		workM=tempN;
	}
	
	static int[] cmd1(int[] xy) {
		int row = xy[0];
		int col = xy[1];
		
		int nrow = (workN-1)-row;
		int ncol = col;
		int[] next = {nrow,ncol};
		return next;
	}
	
	static int[] cmd2(int[] xy) {
		int row = xy[0];
		int col = xy[1];
		
		int nrow = row;
		int ncol = (workM-1)-col;
		int[] next = {nrow,ncol};
		return next;
	}
	
	static int[] cmd3(int[] xy) {
		int row = xy[0];
		int col = xy[1];
		
		int nrow = col;
		int ncol = (workN-1)-row;
		int[] next = {nrow,ncol};
		swap(); // 회전 작업 다 하고 스왑
		return next;
	}
	
	static int[] cmd4(int[] xy) {
		xy = cmd3(xy);
		xy = cmd3(xy);
		xy = cmd3(xy);
		return xy;
	}
	
	static int[] cmd5(int[] xy) { // 디버깅 포인트1. 영역 4분할 위치 잘못적음. // 디버깅 포인트2. else if 조건문에 workN과 workM을 바꿔적음.
		int row = xy[0];
		int col = xy[1];
		
		// 1번
		if(row<workN/2 && col<workM/2) {
			int nrow = row;
			int ncol = col+workM/2;
			int[] next = {nrow,ncol};
			return next;
		}
		// 2번
		else if(row<workN/2 && col>=workM/2) {
			int nrow = row+workN/2;
			int ncol = col;
			int[] next = {nrow,ncol};
			return next;
		}
		// 3번
		else if(row>=workN/2 && col>=workM/2) {
			int nrow = row;
			int ncol = col-workM/2;
			int[] next = {nrow,ncol};
			return next;
		}
		// 4번
		else{//if(row>=workM/2 && col<workN/2) {
			int nrow = row-workN/2;
			int ncol = col;
			int[] next = {nrow,ncol};
			return next;
		}
	}
	
	static int[] cmd6(int[] xy) {
		xy = cmd5(xy);
		xy = cmd5(xy);
		xy = cmd5(xy);
		return xy;
	}
	
	
	// 메인
	public static void main(String[] args) throws Exception {
		// 입력
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		R = Integer.parseInt(tokens.nextToken());
		origin = new int[N][M];
		for (int row = 0; row < N; row++) {
			tokens = new StringTokenizer(input.readLine());
			for (int col = 0; col < M; col++) {
				origin[row][col] = Integer.parseInt(tokens.nextToken());
			}
		}
		cmds = new int[R];
		tokens = new StringTokenizer(input.readLine());
		for (int i = 0; i < R; i++) {
			cmds[i] = Integer.parseInt(tokens.nextToken());
		}
		// 세팅
		int count=0;
		for (int i = 0; i < cmds.length; i++) {
			if(cmds[i]==3 || cmds[i]==4) { // 디버깅 포인트3. || 로 묶어야되는데 실수로 &&로 묶음
				count++;
			}
		}
//		System.out.println(Arrays.toString(cmds));
//		System.out.println("count: "+count);
		if(count%2==0) {
			answer = new int[N][M];
		} else { // 홀수번 90도 회전하면 행열 길이가 서로 바뀜
			answer = new int[M][N];
		}
//		System.out.println(Arrays.deepToString(answer));
		// 작업
		for (int row = 0; row < N; row++) {
			for (int col = 0; col < M; col++) {
				reset(); // 셀마다 리셋
				int value = origin[row][col];
				int[] xy = {row,col};
				for (int i = 0; i < cmds.length; i++) {
					int cmd = cmds[i];
					if(cmd==1)
						xy=cmd1(xy);
					if(cmd==2)
						xy=cmd2(xy);
					if(cmd==3)
						xy=cmd3(xy);
					if(cmd==4)
						xy=cmd4(xy);
					if(cmd==5)
						xy=cmd5(xy);
					if(cmd==6)
						xy=cmd6(xy);
				}
				answer[xy[0]][xy[1]] = value; // 정답의 좌표를 구했으니 값을 저장한다.
			}
		}
		
		// 출력값 만들기
		for (int row = 0; row < answer.length; row++) {
			for (int col = 0; col < answer[0].length; col++) {
				output.append(answer[row][col]).append(" ");
			}
			output.append("\n");
		}
		// 출력
		System.out.println(output);
	}// 메인
}

퍼포먼스

[ 296,584 KB | 472 ms ]

마무리

4,6번을 다이렉트로 계산해도 되지만, 어차피 시간복잡도는 같으므로 빠른 풀이를 위해 재사용했다.