17470번: 배열 돌리기 5
크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 →
www.acmicpc.net
하... 문제의 '배열 돌리기 5'입니다.
정답 비율 16.667%에 달하는 무시무시한 문제입니다.
게다가 제가 사용하는 Java8 기준으로는 정답자가 단 3명밖에 없습니다.
결론적으로 말씀드리자면 못풀었습니다. 원인은 찾았는데 해결 방법을 못찾겠어요.
우선 기본적인 문제 자체는 '배열 돌리기 3'과 같습니다.
16935번: 배열 돌리기 3
크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 →
www.acmicpc.net
어떤 배열을 주고, 입력될 연산을 수행하면 되는 문제입니다. 1번부터 6번까지 각각
상하 반전, 좌우 반전,
오른쪽으로 90도 회전, 왼쪽으로 90도 회선,
배열을 4방위로 4개로 쪼개서 오른쪽으로 돌리기, 왼쪽으로 돌리기
의 총 6가지 연산이 있고, 이를 순서대로 수행해주면 되는 문제입니다.
그럼 배열 돌리기 5가 3과 다른 점이 무엇이냐? 바로 시간 제한은 2초에서 1초로 반으로 줄여놓고 연산의 최대 갯수를 1000개에서 2000000개로 늘려버리는 어마무시한 제한조건을 걸어버립니다.
처음 이 문제를 봤을 때에는 이미 배열 돌리기 3을 풀었던지라 바로 가져와서 제출해봤는데 여지없이 시간초과 당했습니다. 그래서 처음 생각한건 제가 짠 연산들보다 더 효율적인 코드가 있는지였습니다.
아래가 제가 처음으로 짠 배열 돌리기 3 코드입니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main_16935_배열돌리기3_내코드 {
private static int[][] arr;
private static int[][] arr2;
private static int N, M, R;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuffer sb = new StringBuffer();
int temp;
StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(tk.nextToken());
M = Integer.parseInt(tk.nextToken());
R = Integer.parseInt(tk.nextToken());
arr = new int[N][M];
for(int i = 0; i < N; i++) {
tk = new StringTokenizer(br.readLine(), " ");
for(int j = 0; j < M; j++) {
arr[i][j] = Integer.parseInt(tk.nextToken());
}
}
tk = new StringTokenizer(br.readLine(), " ");
for(int i = 0; i < R; i++) {
switch(Integer.parseInt(tk.nextToken())) {
case 1:
operate1();
break;
case 2:
operate2();
break;
case 3:
operate3(M+N+M-1-1-1, 0, N, M);
temp = N;
N = M;
M = temp;
arr = new int[N][M];
for(int j = 0; j < N; j++) {
for(int k = 0; k < M; k++) {
arr[j][k] = arr2[j][k];
}
}
break;
case 4:
operate4(M-1, 0, N, M);
temp = N;
N = M;
M = temp;
arr = new int[N][M];
for(int j = 0; j < N; j++) {
for(int k = 0; k < M; k++) {
arr[j][k] = arr2[j][k];
}
}
break;
case 5:
operate5();
break;
case 6:
operate6();
break;
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
sb.append(arr[i][j]).append(" ");
}sb.append("\n");
}
System.out.println(sb.toString());
}
private static void operate1() {
for(int i = 0; i < N/2; i++) {
for(int j = 0; j < M; j++) {
int temp = arr[i][j];
arr[i][j] = arr[N-1 - i][j];
arr[N-1 - i][j] = temp;
}
}
}
private static void operate2() {
for(int i = 0; i < N; i++) {
for(int j = 0; j < M/2; j++) {
int temp = arr[i][j];
arr[i][j] = arr[i][M-1 - j];
arr[i][M-1 - j] = temp;
}
}
}
// rotateCnt = N-1, 이후 -2씩
// i는 시작 index
// n, m은 각각 해당 단계에서 돌릴 arr의 size
private static void operate3(int rotateCnt, int i, int n, int m) {
Queue<Integer> que = new ArrayDeque<>();
if(n<2 || m<2) return;
for(int k = 0; k < m-1; k++) que.add(arr[i][i+k]);
for(int k = 0; k < n-1; k++) que.add(arr[i+k][i+m-1]);
for(int k = 0; k < m-1; k++) que.add(arr[i+n-1][i+m-1-k]);
for(int k = 0; k < n-1; k++) que.add(arr[i+n-1-k][i]);
for(int k = 0; k < rotateCnt; k++) que.add(que.poll());
if(n == N) {
arr2 = new int[M][N];
}
for(int k = 0; k < n-1; k++) arr2[i][i+k] = que.poll();
for(int k = 0; k < m-1; k++) arr2[i+k][i+n-1] = que.poll();
for(int k = 0; k < n-1; k++) arr2[i+m-1][i+n-1-k] = que.poll();
for(int k = 0; k < m-1; k++) arr2[i+m-1-k][i] = que.poll();
operate3(rotateCnt-6 ,i+1 ,n-2 ,m-2);
}
private static void operate4(int rotateCnt, int i, int n, int m) {
Queue<Integer> que = new ArrayDeque<>();
if(n<2 || m<2) return;
for(int k = 0; k < m-1; k++) que.add(arr[i][i+k]);
for(int k = 0; k < n-1; k++) que.add(arr[i+k][i+m-1]);
for(int k = 0; k < m-1; k++) que.add(arr[i+n-1][i+m-1-k]);
for(int k = 0; k < n-1; k++) que.add(arr[i+n-1-k][i]);
for(int k = 0; k < rotateCnt; k++) que.add(que.poll());
if(n == N) {
arr2 = new int[M][N];
}
for(int k = 0; k < n-1; k++) arr2[i][i+k] = que.poll();
for(int k = 0; k < m-1; k++) arr2[i+k][i+n-1] = que.poll();
for(int k = 0; k < n-1; k++) arr2[i+m-1][i+n-1-k] = que.poll();
for(int k = 0; k < m-1; k++) arr2[i+m-1-k][i] = que.poll();
operate4(rotateCnt-2 ,i+1 ,n-2 ,m-2);
}
private static void operate5() {
int[][] temp = new int[N/2][M/2];
for(int i = 0; i < N/2; i++) {
for(int j = 0; j < M/2; j++) {
temp[i][j] = arr[i][j];
arr[i][j] = arr[i+N/2][j];
arr[i+N/2][j] = arr[i+N/2][j+M/2];
arr[i+N/2][j+M/2] = arr[i][j+M/2];
arr[i][j+M/2] = temp[i][j];
}
}
}
private static void operate6() {
int[][] temp = new int[N/2][M/2];
for(int i = 0; i < N/2; i++) {
for(int j = 0; j < M/2; j++) {
temp[i][j] = arr[i][j];
arr[i][j] = arr[i][j+M/2];
arr[i][j+M/2] = arr[i+N/2][j+M/2];
arr[i+N/2][j+M/2] = arr[i+N/2][j];
arr[i+N/2][j] = temp[i][j];
}
}
}
}
보시면 3번과 4번의 90도 돌리는 연산은 queue에 넣고 회전에 맞춰 앞의 element를 뒤로 돌린 뒤 다시 배열에 넣는 방식으로 구현했습니다. 다른 연산들도 조금씩 고쳤지만 3, 4번이 가장 큰 변화를 받았습니다.
private static void operate3() {
int[][] result = new int[M][N];
for(int r = 0 ; r < N ; ++r) {
for(int c = 0 ; c < M ; ++c) {
result[c][N - 1 - r] = arr[r][c];
}
}
arr = result;
}
private static void operate4() {
int[][] result = new int[M][N];
for(int r = 0 ; r < M ; ++r) {
for(int c = 0 ; c < N ; ++c) {
result[r][c] = arr[c][M - 1 - r];
}
}
arr = result;
}
이건 바꾼 후 90도 회전 코드입니다. 사실 이 코드는 더 효율적인 코드가 없는지 구글링하다가 발견한 코드입니다.
(출처 : https://velog.io/@hyeon930/BOJ-16935-%EB%B0%B0%EC%97%B4-%EB%8F%8C%EB%A6%AC%EA%B8%B03-Java)
수많은 for문들을 혁신적으로 줄여주었습니다. 이 방법으로 연산 시간자체는 최적화되었다고 판단했습니다.
저는 배열 돌리기 5를 풀면서, 어차피 전부 시간초과가 뜨니 연산의 개량을 배열돌리기 3에서 소요되는 시간을 기준으로 생각했습니다.
아래 스크린샷이 제가 제출한 배열돌리기3의 결과들인데요, 1100ms대의 시간에서 300ms대의 시간으로 확 줄어든 것을 볼 수 있습니다.
이로써 연산은 전부 개량을 마쳤는데도 불구하고 여전히 배열돌리기 5에서는 시간초과만 발생했습니다.
그래서 생각을 바꿔서 3에서 5로 바뀌었을 때 가장 큰 변화였던 연산의 양을 줄이고자 생각했습니다.
가만 생각해보면 상하 반전(1번)이나 좌우 반전(2번)은 연속해서 2번 나오면 상쇄되고, 오른쪽으로 90도 회전(3번)과 왼쪽으로 90도 회전(4번)도 번갈아 나오게되면 서로 상쇄되어 없어집니다. 우로 돌리기(5번)과 좌로 돌리기(6번) 또한 마찬가지이며, 1, 2, 1, 2 또는 2, 1, 2, 1의 순서로 나오게 되도 마찬가지 입니다.
(예를 들면 1 2
3 4 일때,
1번 2번 1번 2번
3 4 4 3 2 1 1 2
1 2 2 1 4 3 3 4
이런식으로 다시 돌아오게 됩니다.)
그리고 3, 3, 3, 3, 3, 3, ... 이런식으로 한가지 연산만 연속적으로 나올 때에는, 1번과 2번은 '% 2'로, 3번 ~ 6번은 '% 4'로 각 수로 나눈 나머지를 구해주면 해당 연산과 동일해집니다.
이런 저런 꼼수들을 전부 동원해서 코드를 짠 것이 아래의 코드입니다.
주석처리 해놓은 코드들을 활성화시키면 각 단계들에 소요되는 시간도 출력할 수 있습니다.
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main_16935_배열돌리기5_다시 {
private static int[][] arr;
private static int N, M, R;
static class Problem{
String number;
int count;
public Problem() {};
public Problem(String number, int count) {
this.number = number;
this.count = count;
}
public String toString() {
return "[" + number + " " + count + "]";
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new FileReader("input.txt"));
StringBuffer sb = new StringBuffer();
int temp;
StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(tk.nextToken());
M = Integer.parseInt(tk.nextToken());
R = Integer.parseInt(tk.nextToken());
arr = new int[N][M];
// long beforeTime = System.currentTimeMillis(); //코드 실행 전에 시간 받아오기
for(int i = 0; i < N; i++) {
tk = new StringTokenizer(br.readLine(), " ");
for(int j = 0; j < M; j++) {
arr[i][j] = Integer.parseInt(tk.nextToken());
}
}
// long afterTime = System.currentTimeMillis(); // 코드 실행 후에 시간 받아오기
// long secDiffTime = (afterTime - beforeTime)/1000; //두 시간에 차 계산
// System.out.println("arr input 시간(m) : "+secDiffTime);
String[] inputProblem = new String [R];
Problem[] problems = new Problem[R];
int end = -1;
String back = "0";
// beforeTime = System.currentTimeMillis(); //코드 실행 전에 시간 받아오기
// StringTokenizer말고 다른 방법 찾아보자.
String str = br.readLine();
// tk = new StringTokenizer(str, " ");
String[] str2 = str.split("");
// afterTime = System.currentTimeMillis(); // 코드 실행 후에 시간 받아오기
// secDiffTime = (afterTime - beforeTime)/1000; //두 시간에 차 계산
// System.out.println("String input 시간(m) : "+secDiffTime);
// beforeTime = System.currentTimeMillis(); //코드 실행 전에 시간 받아오기
for(int i = 0; i < R; i++) {
// inputProblem[i] = tk.nextToken();
inputProblem[i] = str2[i];
}
// afterTime = System.currentTimeMillis(); // 코드 실행 후에 시간 받아오기
// secDiffTime = (afterTime - beforeTime)/1000; //두 시간에 차 계산
// System.out.println("problem input + 쪼개기 시간(m) : "+secDiffTime);
//
// beforeTime = System.currentTimeMillis(); //코드 실행 전에 시간 받아오기
for(int i = 0; i < R; i++) {
if(end == -1) {
problems[0] = new Problem(inputProblem[i], 1);
back = problems[0].number;
end = 0;
continue;
}
String t1 = inputProblem[i];
if(back == t1) {
problems[end].count++;
}else {
if(back.equals("3") && t1.equals("4")) {
problems[end].count--;
if(problems[end].count == 0) {
end--;
if(end > -1) back = problems[end].number;
}
}else if(back.equals("4") && t1.equals("3")) {
problems[end].count--;
if(problems[end].count == 0) {
end--;
if(end > -1) back = problems[end].number;
}
}else if(back.equals("5") && t1.equals("6")) {
problems[end].count--;
if(problems[end].count == 0) {
end--;
if(end > -1) back = problems[end].number;
}
}else if(back.equals("6") && t1.equals("5")) {
problems[end].count--;
if(problems[end].count == 0) {
end--;
if(end > -1) back = problems[end].number;
}
}else if(back.equals("1") && t1.equals("1")) {
problems[end].count--;
if(problems[end].count == 0) {
end--;
if(end > -1) back = problems[end].number;
}
}else if(back.equals("2") && t1.equals("2")) {
problems[end].count--;
if(problems[end].count == 0) {
end--;
if(end > -1) back = problems[end].number;
}
}else if(i < R-3 && back.equals("1") && inputProblem[i].equals("2") && inputProblem[i+1].equals("1") && inputProblem[i+2].equals("2")) {
problems[end].count--;
if(problems[end].count == 0) {
end--;
if(end > -1) back = problems[end].number;
}
i = i + 2;
}else if(i < R-3 && back.equals("2") && inputProblem[i].equals("1") && inputProblem[i+1].equals("2") && inputProblem[i+2].equals("1")) {
problems[end].count--;
if(problems[end].count == 0) {
end--;
if(end > -1) back = problems[end].number;
}
i = i + 2;
}else if(i < R-3 && back.equals("3") && inputProblem[i].equals("3") && inputProblem[i+1].equals("3") && inputProblem[i+2].equals("3")) {
problems[end].count--;
if(problems[end].count == 0) {
end--;
if(end > -1) back = problems[end].number;
}
i = i + 2;
}else if(i < R-3 && back.equals("4") && inputProblem[i].equals("4") && inputProblem[i+1].equals("4") && inputProblem[i+2].equals("4")) {
problems[end].count--;
if(problems[end].count == 0) {
end--;
if(end > -1) back = problems[end].number;
}
i = i + 2;
}else {
end++;
problems[end] = new Problem(t1, 1);
back = t1;
}
}
}
// afterTime = System.currentTimeMillis(); // 코드 실행 후에 시간 받아오기
// secDiffTime = (afterTime - beforeTime)/1000; //두 시간에 차 계산
// System.out.println("전처리 시간(m) : "+secDiffTime);
// for(int i = 0; i < end+1; i++) {
// System.out.println(problems[i].toString());
// }
// beforeTime = System.currentTimeMillis(); //코드 실행 전에 시간 받아오기
for(int i = 0; i < end+1; i++){
switch(problems[i].number) {
case "1":
for(int j = 0; j < (problems[i].count % 2); j++) {
operate1();
}
break;
case "2":
for(int j = 0; j < (problems[i].count % 2); j++) {
operate2();
}
break;
case "3":
for(int l = 0; l < problems[i].count % 4; l++) {
operate3();
temp = N;
N = M;
M = temp;
}
break;
case "4":
for(int l = 0; l < problems[i].count % 4; l++) {
operate4();
temp = N;
N = M;
M = temp;
}
break;
case "5":
for(int j = 0; j < (problems[i].count % 4); j++) {
operate5();
}
break;
case "6":
for(int j = 0; j < (problems[i].count % 4); j++) {
operate6();
}
break;
}
}
// afterTime = System.currentTimeMillis(); // 코드 실행 후에 시간 받아오기
// secDiffTime = (afterTime - beforeTime)/1000; //두 시간에 차 계산
// System.out.println("실제 이동 시간(m) : "+secDiffTime);
//
//
// beforeTime = System.currentTimeMillis(); //코드 실행 전에 시간 받아오기
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
sb.append(arr[i][j]).append(" ");
}sb.append("\n");
}
System.out.println(sb.toString());
// afterTime = System.currentTimeMillis(); // 코드 실행 후에 시간 받아오기
// secDiffTime = (afterTime - beforeTime)/1000; //두 시간에 차 계산
// System.out.println("출력 시간(m) : "+secDiffTime);
br.close();
}
private static void operate1() {
for(int i = 0; i < N/2; i++) {
int[] temp = arr[i];
arr[i] = arr[N-1-i];
arr[N-1-i] = temp;
}
}
private static void operate2() {
for(int i = 0; i < N; i++) {
for(int j = 0; j < M/2; j++) {
int temp = arr[i][j];
arr[i][j] = arr[i][M-1 - j];
arr[i][M-1 - j] = temp;
}
}
}
// rotateCnt = N-1, 이후 -2씩
// i는 시작 index
// n, m은 각각 해당 단계에서 돌릴 arr의 size
// https://velog.io/@hyeon930/BOJ-16935-%EB%B0%B0%EC%97%B4-%EB%8F%8C%EB%A6%AC%EA%B8%B03-Java
private static void operate3() {
int[][] result = new int[M][N];
for(int r = 0 ; r < N ; ++r) {
for(int c = 0 ; c < M ; ++c) {
result[c][N - 1 - r] = arr[r][c];
}
}
arr = result;
}
private static void operate4() {
int[][] result = new int[M][N];
for(int r = 0 ; r < M ; ++r) {
for(int c = 0 ; c < N ; ++c) {
result[r][c] = arr[c][M - 1 - r];
}
}
arr = result;
}
private static void operate5() {
int[][] temp = new int[N/2][M/2];
for(int i = 0; i < N/2; i++) {
for(int j = 0; j < M/2; j++) {
temp[i][j] = arr[i][j];
arr[i][j] = arr[i+N/2][j];
arr[i+N/2][j] = arr[i+N/2][j+M/2];
arr[i+N/2][j+M/2] = arr[i][j+M/2];
arr[i][j+M/2] = temp[i][j];
}
}
}
private static void operate6() {
int[][] temp = new int[N/2][M/2];
for(int i = 0; i < N/2; i++) {
for(int j = 0; j < M/2; j++) {
temp[i][j] = arr[i][j];
arr[i][j] = arr[i][j+M/2];
arr[i][j+M/2] = arr[i+N/2][j+M/2];
arr[i+N/2][j+M/2] = arr[i+N/2][j];
arr[i+N/2][j] = temp[i][j];
}
}
}
}
사실 전처리를 마치고 배열 돌리기 3에서 정상적으로 작동했을 때, 저는 이 문제를 푼줄 알고 기뻐했습니다.
하지만 여전히 배열 돌리기 5의 벽은 높았고, 시간 초과가 저를 기다리고 있었습니다.
사실 이쯤오니 이제는 궁금하더군요. 분명 데이터의 전처리도 제대로 했고, 각 연산들도 최적화가 된 것 같은데 왜 안풀리는거지??
그래서 각 단계에 소요되는 시간들을 알아보았습니다. 그랬더니 충격적인 결과를 볼 수 있었습니다.
배열돌리기5 200만개 input했을 때 걸린 시간 (StringTokenizer)
arr input 시간(m) : 0
StringTokenizer input 시간(m) : 311
problem input 시간(m) : 0
전처리 시간(m) : 0
실제 이동 시간(m) : 0
3 9 5 2 1 4
2 7 9 1 3 5
6 8 2 3 2 1
3 2 1 8 8 9
1 1 9 6 7 8
2 4 6 3 9 2
9 5 1 9 2 1
7 3 8 2 1 3
출력 시간(m) : 0
배열돌리기5 200만개 input했을 때 걸린 시간 (split)
arr input 시간(m) : 0
split input 시간(m) : 294
problem input 시간(m) : 0
전처리 시간(m) : 0
실제 이동 시간(m) : 0
3 9 5 2 1 4
2 7 9 1 3 5
6 8 2 3 2 1
3 2 1 8 8 9
1 1 9 6 7 8
2 4 6 3 9 2
9 5 1 9 2 1
7 3 8 2 1 3
출력 시간(m) : 0
다른 방법
2arr input 시간(m) : 0
String input 시간(m) : 267
problem input + 쪼개기 시간(m) : 0
전처리 시간(m) : 0
근데 결국엔 String input 시간 자체가 너무 길다.
시간을 잡아먹고 있던건 전처리도, 연산도 아닌 바로 input이었습니다. 그것도 정확하게는 br.readLine()으로 문자 200만개 + 공백 200만개의 총 400만개의 문자가 들어있는 line을 읽어올 때 저만큼의 시간이 잡아먹혔습니다.
그래서 저는 더 효율적인 read 방법이 있을거라 생각해서 열심히 구글링을 해보았지만 BufferedReader 이상으로 빠른 read 방법을 찾지 못하였습니다.
그래서 결국 저의 '배열 돌리기 5' 풀기 도전은 여기서 마감하였습니다.
백준의 데이터베이스에는 이 문제를 Java 8로 해결하신 분들이 3분 계시니 분명 방법은 있었을 것입니다. 하지만 저로써는 이 이상의 방법을 찾지 못했습니다.
혹여나 더 도전하실 분들을 위해 제가 만들어 사용했던 input 파일을 올려놓겠습니다.
끝으로 비록 이번 문제를 풀지는 못했지만 몰랐던 방법들이라던가 Java의 read 방법들, 구분자를 이용해 문자열을 쪼개는 방법들, 데이터를 전처리해야하는 필요성 등등 효율성에 관련된 생각을 많이할 수 있었기 때문에 굉장히 유용한 시간이었습니다.
혹시 방법을 아시는 분이 계시다면 알려주시면 감사하겠습니다!
'컴쟁이의 알고리즘' 카테고리의 다른 글
| 백준 1759번 - 암호 만들기 (0) | 2021.03.16 |
|---|---|
| 백준 알고리즘 - 2477 참외밭 (0) | 2021.02.21 |
| 백준 알고리즘 - 15686 치킨 배달 (0) | 2021.02.17 |
| 백준 알고리즘 - 9742 순열 (0) | 2021.02.16 |
| 백준 알고리즘 - 2839 설탕 배달 (0) | 2021.02.16 |