여태 깨작깨작 PS를 하면서 어려운 문제들을 많이 만났다. 개중에는 지금 돌아보면 아무 것도 아닌 문제도 있지만,그 때는 또 그만큼 실력이 더 모자랐기 때문에... 브론즈 I/O 문제조차 당황하며 하루 종일 잡고 있던 때가 있었으니.
그런데 이 문제만큼 '볼륨'이 크다고 느낀 문제는 처음이었다. 보자마자 아, 그냥 튈까 하고 생각했지만 결국 극복해내지 못하면 다음 단계로 나아가지 못하기에 차분히 손을 댔다.
20327번: 배열 돌리기 6 (acmicpc.net) // 문제 예시가 너무 길어 링크로 첨부
아직 완전한 리뷰가 아니기에 간단하게만 쓰면, 배열의 부분배열들을 변경시키는 함수 8개를 구현해야 한다. 상하반전, 좌우반전, 우로 90도/좌로 90도 회전, 그리고 똑같은 논리로 '부분배열 자체'를 이동시키는 함수들을 구현해야 한다. 나는 오늘 앞의 4개를 구현하였다.
먼저, 상하 반전과 좌우 반전의 경우에는 스택을 이용해서 구현하였다.
static void upsideDown(int[][] targetArr,int l,int startRow){
int subArrLen = (int)Math.pow(2,l);
if(startRow>=targetArr.length){
return;
}
Stack<Integer> upper = new Stack<>();
Stack<Integer> lower = new Stack<>();
for(int i=startRow;i<startRow+subArrLen/2;i++){
for(int j=0;j<targetArr[i].length;j++){
upper.push(targetArr[i][j]);
}
}
for(int i=startRow+subArrLen/2;i<startRow+subArrLen;i++){
for(int j=0;j<targetArr[i].length;j++){
lower.push(targetArr[i][j]);
}
}이것이 상하반전의 경우이고, 좌우반전의 경우에도 똑같다. 다만 위/아래가 좌/우로 바뀌었을 뿐이다.
=> 하루가 지나고 생각해 보니, 왜 굳이 스택을 사용했는지 모르겠다는 생각이 들었다. 그래서 마찬가지로 큐를 사용하는 것으로 수정했다.
그것보다 중요한 수정은, l=0인 경우를 고려하지 않았다는 점이다. 이 부분은 백준이 친절하게 테케를 제공해 준 덕분에 캐치할 수 있었다. 1~4번에 해당하는 연산은 부분수열 '내에서의' 연산이기 때문에 l=0인 경우 뭘 건드려서는 안 된다. 따라서 1~4번 함수에 모두 l=0일 때 탈출하도록 탈출조건을 추가해 주었다.
또한, 1번 연산의 경우 l=2인 경우 이상하게 가동되고, 2번 연산의 경우 l=1인 경우 이상하게 가동되는 것을 테케들을 돌려보면서 확인하였다. 가장 최악의 경우인 "맞는 것 같은데 특정 인풋에서만 틀려버리는 코드"를 구현한 것이다... 백준이 테케를 잘 주지 않았으면 영원히 잡고 있었을지도...
2번 함수(좌우반전)의 경우에는 1번 함수(상하반전)의 경우와 같기에, 상하반전의 경우만 설명하려고 한다. 나는 startRow를 인풋으로 받고, rowIdx를 설정하여 while문을 통해 부분배열의 최상단-최하단, 최상단+1-최하단-1... 이 각각 교체되게 하였다. 수정된 코드는 아래와 같다.
static void upsideDown(int[][] targetArr,int l,int startRow){
if(l<=0){
return;
}
int subArrLen = (int)Math.pow(2,l);
if(subArrLen>targetArr.length){
return;
}
if(startRow>=targetArr.length){
return;
}
int rowIdx = 0;
while(rowIdx<subArrLen/2){
Queue<Integer> upper = new LinkedList<>();
Queue<Integer> lower = new LinkedList<>();
for(int i=0;i<targetArr.length;i++){
upper.offer(targetArr[startRow+rowIdx][i]);
lower.offer(targetArr[startRow+subArrLen-rowIdx-1][i]);
}
for(int i=0;i<targetArr.length;i++){
targetArr[startRow+rowIdx][i] = lower.poll();
targetArr[startRow+subArrLen-rowIdx-1][i] = upper.poll();
}
rowIdx++;
}
upsideDown(targetArr, l, startRow+subArrLen);
}2번의 경우에는 row를 다루는 부분을 col을 다루도록 잘 만져주면 된다.
회전의 경우에는 지난 문제와 비슷했다. 큐를 이용해 구현하였다.
static void rotateLeft(int[][] targetArr,int l,int init,int startRow,int startCol){
int subArrLen = (int)Math.pow(2,l);
if(init>=subArrLen/2){
/*
만일 가로(col) 방향으로 아직 회전시키지 않은 부분배열이 있을 경우 그 부분배열 작업
가로방향으로 모든 부분배열을 회전시켰을 경우에는, 세로 방향으로 내려와서 첫 가로방향 부분배열부터 다시 작업
만일 가로, 세로 모든 부분배열 작업을 완료했을 경우에는 탈출
*/
if(startCol<targetArr.length-subArrLen && startRow<targetArr.length-subArrLen){
rotateLeft(targetArr,l,0,startRow,startCol+subArrLen);
}else if(startCol>= targetArr.length-subArrLen&&startRow<targetArr.length-subArrLen){
rotateLeft(targetArr,l,0,startRow+subArrLen,0);
}else{
return;
}
}else{
Queue<Integer> queue = new LinkedList<>();
//넣기 _ 좌하우상 순
for(int i=startRow+init;i<startRow+subArrLen-init-1;i++){
queue.offer(targetArr[i][startCol+init]);
}
for(int i=startCol+init;i<startCol+subArrLen-init-1;i++){
queue.offer(targetArr[startRow+subArrLen-init-1][i]);
}
for(int i = startRow+subArrLen-init-1;i>=startRow+init+1;i--){
queue.offer(targetArr[i][startCol+subArrLen-init-1]);
}
for(int i=startCol+subArrLen-init-1;i>=startCol+init+1;i--){
queue.offer(targetArr[startRow+init][i]);
}
//채우기_하단부터
for(int i=startCol+init;i<startCol+subArrLen-init-1;i++){
targetArr[startRow+subArrLen-init-1][i] = queue.poll();
}
for(int i=startRow+subArrLen-init-1;i>=startRow+init+1;i--){
targetArr[i][startCol+subArrLen-init-1] = queue.poll();
}
for(int i=startCol+subArrLen-init-1;i>=startCol+init+1;i--){
targetArr[startRow+init][i]= queue.poll();
}
for(int i=startRow+init;i<startRow+subArrLen-init-1;i++){
targetArr[i][startCol+init] = queue.poll();
}
rotateLeft(targetArr,l,init+1,startRow,startCol);
}
}이것이 좌로 90도 회전시키는 경우이고, 우로 회전시키는 경우에도 똑같은 논리로 조금만 바꿔 주면 된다.
=> 이 부분도 약간의 수정을 거쳤다. 탈출조건에서 에러가 난 부분인데, 가로 방향으로 부분배열 작업을 완료하고 다시 내려와서 작업하는 로직에서, 마지막 줄을 작업할 때 첫 번째 부분배열만 작업하고 그대로 종료해 버리는 문제가 발생했다.
즉, startRow>=targetArr.length-subArrLen인데 startCol<targetArr.length-subArrLen인 경우에 대해 처리가 안 된 것이다.
다음과 같이 탈출조건을 수정하여서 해결하였다.
if(startCol<targetArr.length-subArrLen){
rotateLeft(targetArr,l,0,startRow,startCol+subArrLen);
}else if(startCol>= targetArr.length-subArrLen&&startRow<targetArr.length-subArrLen){
rotateLeft(targetArr,l,0,startRow+subArrLen,0);
}else{
return;
}
이 부분에서 StackOverFlow 에러가 발생하여 고생을 했다. 그리고 그 문제는 탈출조건을 만족하지 않았을 때 수행할 식을 else문 안으로 넣어 주어서 해결했다.
여태까지의 내 스타일이, 탈출 조건만 if문으로 작성하고 따로 else문을 쓰지 않고 그냥 그 밑으로 함수를 죽 써 주는 스타일이었다. 아직 왜 StackOverFlow가 났는지 확실하게는 잘 모르겠지만, 아마 특정 조건을 만족하면 바로 탈출시켜주는 경우가 아니라 특정 조건을 만족한 경우에 거기서 또 다른 조건을 만족해야 탈출시키고 아닌 경우 다시 함수를 호출하기 때문에, 다시 함수를 호출해 놓고 if문을 탈출해서 아래로 내려가서 또 기존 flow 대로 따라가려다가 StackOverFlow가 발생한 것은 아닐까 추측해 본다.
각 조건마다 새로운 재귀함수를 호출하고 return 해도 될 것 같다는 생각이 들었는데, 오늘 뇌 용량을 너무 많이 써서 그냥 넘어갔다... 그냥 깔끔하게 else문 안에 넣으련다.
3,4 의 경우에는 거의 모든 코드가 똑같고, 다만 큐에 넣은 배열의 요소들을 다시 때려박는 방식만 수정해 주면 된다. 물론 어디서부터 다시 넣어야 할지 고민해보면서 머리에서 조금 김이 났지만, 그냥 찬찬히 생각해 보면서 하면 된다.
5~8번의 경우에는 "부분배열 자체"를 이동시켜야 한다. 따라서 l=0이라서 배열의 한 칸 한 칸이 모두 부분배열이 되더라도 작업을 해 주어야 한다. 따라서 l<=0일 때 함수를 바로 return하는 조건을 제거해 주어야 한다.
마찬가지로 5-6(상하, 좌우반전)의 논리가 같고 7-8(좌회전, 우회전)의 논리가 같기에 5번, 8번만 코드를 복기해 보려 한다.
5번 상하반전의 경우, 함수의 매개변수로 startRow와 endRow를 모두 받아서, endRow가 startRow보다 작거나 같아지는 순간에 재귀함수를 탈출하게 하였다.
기본적인 구현 방법은 큐를 이용하여 큐에 값을 넣은 뒤 다시 채워넣는 방식으로 동일하다.
static void upsideDown2(int[][] targetArr,int l,int startRow,int endRow){
int subArrLen = (int)Math.pow(2,l);
if(subArrLen>targetArr.length){
return;
}
if(endRow<=startRow){
return;
}
Queue<Integer> upper = new LinkedList<>();
Queue<Integer> lower = new LinkedList<>();
//상단
for(int i=startRow;i<startRow+subArrLen;i++){
for(int j=0;j<targetArr[i].length;j++){
upper.offer(targetArr[i][j]);
}
}
//하단
for(int i=endRow-subArrLen;i<endRow;i++){
for(int j=0;j<targetArr[i].length;j++){
lower.offer(targetArr[i][j]);
}
}
//채우기
for(int i=endRow-subArrLen;i<endRow;i++){
for(int j=0;j<targetArr[i].length;j++){
targetArr[i][j] = upper.poll();
}
}
for(int i=startRow;i<startRow+subArrLen;i++){
for(int j=0;j<targetArr[i].length;j++){
targetArr[i][j] = lower.poll();
}
}
upsideDown2(targetArr,l,startRow+subArrLen,endRow-subArrLen);
}부분배열 자체의 이동이기 때문에 부분배열의 크기에 따라서 어디가 시작 index이고 어디가 해당 부분배열의 마지막 index이고... 하는 것을 고려할 필요가 없었다. 그냥 부분배열 크기만큼, 배열의 맨 처음과 맨 끝에서부터 바꿔주면 그만이라 오히려 5-6번이 1-2번 보다 쉽게 느껴졌다. 6번은 상하만 좌우로 바꾸고 row를 다루던 것이 col을 다루도록 바꾸면 된다.
7-8번은 이전에 했었던 배열돌리기2와 거의 같다. 배열을 순회해 가며 큐에 값을 넣고, 다시 다른 시작지점부터 배열을 순회하며 큐의 값들을 뱉어내고, 특정 depth이상으로 들어가면 재귀함수를 탈출해 주면 된다. 다만 한 줄을 큐에 채워넣는 게 아니라 '부분배열'을 채워넣어야 한다. 따라서 부분배열 자체를 큐에 어떻게 하면 정확하게 넣을지, 뱉을 때도 어떻게 하면 정확하게 뱉을지 고민하는 것이 꽤 골치 아팠다.
아직 PS 초보이지만 여태 느낀 바로는, 이럴 때는 그냥 종이 한 장 가져다 놓고 체크해 가면서 정공법으로 뚫는 게 가장 나은 것 같다. 시작점부터 출발해서 해당 부분배열의 길이만큼 반복문을 사용해 큐에 값들을 채워넣고 다시 부분배열 길이만큼 이동해서 같은 작업을 반복해야 한다. 뱉을 때도 마찬가지다. 특별한 알고리즘이나 발상의 전환이 필요한 부분이 아니라 노가다이기에 그냥 문답무용 코드로 설명해야 할 것 같다.
static void rotateLeft2(int[][] targetArr,int l,int init){
int subArrLen = (int)Math.pow(2,l);
if(subArrLen>targetArr.length){
return;
}
if(init>=targetArr.length/2){
return;
}
Queue<Integer> queue = new LinkedList<>();
//담기_각 배열 모양대로 담아야 함.
int rowIdx = init;
while(rowIdx< targetArr.length-init-subArrLen){
for(int i=rowIdx;i<rowIdx+subArrLen;i++){
for(int j=init;j<init+subArrLen;j++){
queue.offer(targetArr[i][j]);
}
}
rowIdx+=subArrLen;
}
int colIdx = init;
while(colIdx< targetArr.length-init-subArrLen){
for(int i=targetArr.length-subArrLen-init;i< targetArr.length-init;i++){
for(int j=colIdx;j<colIdx+subArrLen;j++){
queue.offer(targetArr[i][j]);
}
}
colIdx+=subArrLen;
}
while(rowIdx>init){
for(int i=rowIdx;i<rowIdx+subArrLen;i++){
for(int j=targetArr.length-init-subArrLen;j< targetArr.length-init;j++){
queue.offer(targetArr[i][j]); }
}
rowIdx-=subArrLen;
}
while(colIdx>init){
for(int i=init;i<init+subArrLen;i++){
for(int j=colIdx;j<colIdx+subArrLen;j++){
queue.offer(targetArr[i][j]);
}
}
colIdx-=subArrLen;
}
//미뤄서 채우기!
rowIdx = targetArr.length-init-subArrLen;
colIdx = init;
while(colIdx<targetArr.length-init-subArrLen){
for(int i=rowIdx;i<rowIdx+subArrLen;i++){
for(int j=colIdx;j<colIdx+subArrLen;j++){
targetArr[i][j] = queue.poll();
}
}
colIdx+=subArrLen;
//colIdx = targetArr.length-init-subArrLen
}
while(rowIdx>init){
for(int i=rowIdx;i<rowIdx+subArrLen;i++){
for(int j=colIdx;j<colIdx+subArrLen;j++){
targetArr[i][j] = queue.poll();
}
}
rowIdx-=subArrLen;
//rowIdx = init
}
while(colIdx>init){
for(int i=rowIdx;i<rowIdx+subArrLen;i++){
for(int j=colIdx;j<colIdx+subArrLen;j++){
targetArr[i][j] = queue.poll();
}
}
colIdx-=subArrLen;
//colIdx=init
}
while(rowIdx<targetArr.length-init-subArrLen){
for(int i=rowIdx;i<rowIdx+subArrLen;i++){
for(int j=colIdx;j<colIdx+subArrLen;j++){
targetArr[i][j] = queue.poll();
}
}
rowIdx+=subArrLen;
}
rotateLeft2(targetArr,l,init+subArrLen);
}rowIdx, colIdx 변수를 가져와서 큐에 값들을 채워넣고 뱉어내는 데 이용했다. 기존에 init+targetArr.length+subArrLen... +1, -1... 등등을 덕지덕지 붙여가며 끙끙대다가 이렇게 하니 훨씬 낫다는 생각이 들었다. 기존 배열돌리기도 이렇게 할 수 있지 않을까? 하는 생각이 들었지만 엄두가 안 나서 그냥 내버려 두었다.
이로서 1~8번을 모두 구현했고, 본문에는 switch문을 이용해서 문제를 해결했다. 전체 코드를 첨부한다.
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BOJ_20327 {
static int N,R;
static int[][] arr;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] NR = br.readLine().split(" ");
N = Integer.parseInt(NR[0]);
R = Integer.parseInt(NR[1]);
int rowCol = (int)Math.pow(2,N);
arr = new int[rowCol][rowCol];
for(int i=0;i<arr.length;i++){
String[] rowInput = br.readLine().split(" ");
for(int j=0;j<arr[i].length;j++){
arr[i][j] = Integer.parseInt(rowInput[j]);
}
}
for(int i=0;i<R;i++){
String[] orderL = br.readLine().split(" ");
int order = Integer.parseInt(orderL[0]);
int l = Integer.parseInt(orderL[1]);
switch (order){
case 1:
upsideDown(arr,l,0);
break;
case 2:
leftRightReverse(arr,l,0);
break;
case 3:
rotateRight(arr,l,0,0,0);
break;
case 4:
rotateLeft(arr,l,0,0,0);
break;
case 5:
upsideDown2(arr,l,0,arr.length);
break;
case 6:
leftRightReverse2(arr,l,0,arr.length);
break;
case 7:
rotateRight2(arr,l,0);
break;
case 8:
rotateLeft2(arr,l,0);
break;
}
}
br.close();
for(int k=0;k<arr.length;k++){
for(int j=0;j<arr[k].length;j++){
bw.write(arr[k][j]+" ");
}
bw.write("\n");
bw.flush();
}
bw.close();
}
static void leftRightReverse(int[][] targetArr,int l,int startCol){
if(l<=0){
return;
}
int subArrLen = (int)Math.pow(2,l);
if(subArrLen>targetArr.length){
return;
}
if(startCol>=targetArr.length){
return;
}
int colIdx =0;
while(colIdx<subArrLen/2){
Queue<Integer> left = new LinkedList<>();
Queue<Integer> right = new LinkedList<>();
for(int i=0;i<targetArr.length;i++){
left.offer(targetArr[i][startCol+colIdx]);
right.offer(targetArr[i][startCol+subArrLen-colIdx-1]);
}
for(int i=0;i<targetArr.length;i++){
targetArr[i][startCol+colIdx] = right.poll();
targetArr[i][startCol+subArrLen-colIdx-1] = left.poll();
}
colIdx++;
}
leftRightReverse(targetArr, l, startCol+subArrLen);
}
static void upsideDown(int[][] targetArr,int l,int startRow){
if(l<=0){
return;
}
int subArrLen = (int)Math.pow(2,l);
if(subArrLen>targetArr.length){
return;
}
if(startRow>=targetArr.length){
return;
}
int rowIdx = 0;
while(rowIdx<subArrLen/2){
Queue<Integer> upper = new LinkedList<>();
Queue<Integer> lower = new LinkedList<>();
for(int i=0;i<targetArr.length;i++){
upper.offer(targetArr[startRow+rowIdx][i]);
lower.offer(targetArr[startRow+subArrLen-rowIdx-1][i]);
}
for(int i=0;i<targetArr.length;i++){
targetArr[startRow+rowIdx][i] = lower.poll();
targetArr[startRow+subArrLen-rowIdx-1][i] = upper.poll();
}
rowIdx++;
}
upsideDown(targetArr, l, startRow+subArrLen);
}
static void rotateRight(int[][] targetArr,int l,int init,int startRow,int startCol){
if(l<=0){
return;
}
int subArrLen = (int)Math.pow(2,l);
if(subArrLen>targetArr.length){
return;
}
if(init>=subArrLen/2){
if(startCol<targetArr.length-subArrLen){
rotateRight(targetArr,l,0,startRow,startCol+subArrLen);
}else if(startCol>= targetArr.length-subArrLen&&startRow<targetArr.length-subArrLen){
rotateRight(targetArr,l,0,startRow+subArrLen,0);
}else{
return;
}
}else{
Queue<Integer> queue = new LinkedList<>();
for(int i=startRow+init;i<startRow+subArrLen-init-1;i++){
queue.offer(targetArr[i][startCol+init]);
}
for(int i=startCol+init;i<startCol+subArrLen-init-1;i++){
queue.offer(targetArr[startRow+subArrLen-init-1][i]);
}
for(int i = startRow+subArrLen-init-1;i>=startRow+init+1;i--){
queue.offer(targetArr[i][startCol+subArrLen-init-1]);
}
for(int i=startCol+subArrLen-init-1;i>=startCol+init+1;i--){
queue.offer(targetArr[startRow+init][i]);
}
//채우기 - 우상단부터
for(int i=startCol+subArrLen-init-1;i>=startCol+init+1;i--){
targetArr[startRow+init][i] = queue.poll();
}
//좌
for(int i=startRow+init;i<startRow+subArrLen-init-1;i++){
targetArr[i][startCol+init] = queue.poll();
}
//하
for(int i=startCol+init;i<startCol+subArrLen-init-1;i++){
targetArr[startRow+subArrLen-init-1][i]=queue.poll();
}
//우
for(int i=startRow+subArrLen-init-1;i>=startRow+init+1;i--){
targetArr[i][startCol+subArrLen-init-1] = queue.poll();
}
rotateRight(targetArr,l,init+1,startRow,startCol);
}
}
static void rotateLeft(int[][] targetArr,int l,int init,int startRow,int startCol){
if(l<=0){
return;
}
int subArrLen = (int)Math.pow(2,l);
if(subArrLen>targetArr.length){
return;
}
if(init>=subArrLen/2){
/*
만일 가로(col) 방향으로 아직 회전시키지 않은 부분배열이 있을 경우 그 부분배열 작업
가로방향으로 모든 부분배열을 회전시켰을 경우에는, 세로 방향으로 내려와서 첫 가로방향 부분배열부터 다시 작업
만일 가로, 세로 모든 부분배열 작업을 완료했을 경우에는 탈출
*/
if(startCol<targetArr.length-subArrLen){
rotateLeft(targetArr,l,0,startRow,startCol+subArrLen);
}else if(startCol>= targetArr.length-subArrLen&&startRow<targetArr.length-subArrLen){
rotateLeft(targetArr,l,0,startRow+subArrLen,0);
}else{
return;
}
}else{
Queue<Integer> queue = new LinkedList<>();
//넣기 _ 좌하우상 순
for(int i=startRow+init;i<startRow+subArrLen-init-1;i++){
queue.offer(targetArr[i][startCol+init]);
}
for(int i=startCol+init;i<startCol+subArrLen-init-1;i++){
queue.offer(targetArr[startRow+subArrLen-init-1][i]);
}
for(int i = startRow+subArrLen-init-1;i>=startRow+init+1;i--){
queue.offer(targetArr[i][startCol+subArrLen-init-1]);
}
for(int i=startCol+subArrLen-init-1;i>=startCol+init+1;i--){
queue.offer(targetArr[startRow+init][i]);
}
//채우기_하단부터
for(int i=startCol+init;i<startCol+subArrLen-init-1;i++){
targetArr[startRow+subArrLen-init-1][i] = queue.poll();
}
for(int i=startRow+subArrLen-init-1;i>=startRow+init+1;i--){
targetArr[i][startCol+subArrLen-init-1] = queue.poll();
}
for(int i=startCol+subArrLen-init-1;i>=startCol+init+1;i--){
targetArr[startRow+init][i]= queue.poll();
}
for(int i=startRow+init;i<startRow+subArrLen-init-1;i++){
targetArr[i][startCol+init] = queue.poll();
}
rotateLeft(targetArr,l,init+1,startRow,startCol);
}
}
static void upsideDown2(int[][] targetArr,int l,int startRow,int endRow){
int subArrLen = (int)Math.pow(2,l);
if(subArrLen>targetArr.length){
return;
}
if(endRow<=startRow){
return;
}
Queue<Integer> upper = new LinkedList<>();
Queue<Integer> lower = new LinkedList<>();
//상단
for(int i=startRow;i<startRow+subArrLen;i++){
for(int j=0;j<targetArr[i].length;j++){
upper.offer(targetArr[i][j]);
}
}
//하단
for(int i=endRow-subArrLen;i<endRow;i++){
for(int j=0;j<targetArr[i].length;j++){
lower.offer(targetArr[i][j]);
}
}
//채우기
for(int i=endRow-subArrLen;i<endRow;i++){
for(int j=0;j<targetArr[i].length;j++){
targetArr[i][j] = upper.poll();
}
}
for(int i=startRow;i<startRow+subArrLen;i++){
for(int j=0;j<targetArr[i].length;j++){
targetArr[i][j] = lower.poll();
}
}
upsideDown2(targetArr,l,startRow+subArrLen,endRow-subArrLen);
}
static void leftRightReverse2(int[][] targetArr,int l,int startCol,int endCol){
int subArrLen = (int)Math.pow(2,l);
if(subArrLen>targetArr.length){
return;
}
if(endCol<=startCol){
return;
}
Queue<Integer> left = new LinkedList<>();
Queue<Integer> right = new LinkedList<>();
for(int i=0;i<targetArr.length;i++){
for(int j=startCol;j<startCol+subArrLen;j++){
left.offer(targetArr[i][j]);
}
}
for(int i=0;i<targetArr.length;i++){
for(int j=endCol-subArrLen;j<endCol;j++){
right.offer(targetArr[i][j]);
}
}
//바꿔서 채우기
for(int i=0;i<targetArr.length;i++){
for(int j=startCol;j<startCol+subArrLen;j++){
targetArr[i][j] = right.poll();
}
}
for(int i=0;i<targetArr.length;i++){
for(int j=endCol-subArrLen;j<endCol;j++){
targetArr[i][j] = left.poll();
}
}
leftRightReverse2(targetArr,l,startCol+subArrLen,endCol-subArrLen);
}
static void rotateRight2(int[][] targetArr,int l,int init){
int subArrLen = (int)Math.pow(2,l);
if(subArrLen>targetArr.length){
return;
}
if(init>=targetArr.length/2){
return;
}
Queue<Integer> queue = new LinkedList<>();
//담기_각 배열 모양대로 담아야 함.
int rowIdx = init;
while(rowIdx< targetArr.length-init-subArrLen){
for(int i=rowIdx;i<rowIdx+subArrLen;i++){
for(int j=init;j<init+subArrLen;j++){
queue.offer(targetArr[i][j]);
}
}
rowIdx+=subArrLen;
}
int colIdx = init;
while(colIdx< targetArr.length-init-subArrLen){
for(int i=targetArr.length-subArrLen-init;i< targetArr.length-init;i++){
for(int j=colIdx;j<colIdx+subArrLen;j++){
queue.offer(targetArr[i][j]);
}
}
colIdx+=subArrLen;
}
while(rowIdx>init){
for(int i=rowIdx;i<rowIdx+subArrLen;i++){
for(int j=targetArr.length-init-subArrLen;j< targetArr.length-init;j++){
queue.offer(targetArr[i][j]); }
}
rowIdx-=subArrLen;
}
while(colIdx>init){
for(int i=init;i<init+subArrLen;i++){
for(int j=colIdx;j<colIdx+subArrLen;j++){
queue.offer(targetArr[i][j]);
}
}
colIdx-=subArrLen;
}
//미뤄서 채우기!
rowIdx = init;
colIdx = targetArr.length-init-subArrLen;
while(colIdx>init){
for(int i=init;i<init+subArrLen;i++){
for(int j=colIdx;j<colIdx+subArrLen;j++){
targetArr[i][j] = queue.poll();
}
}
colIdx-=subArrLen;
}
while(rowIdx< targetArr.length-init-subArrLen){
for(int i=rowIdx;i<rowIdx+subArrLen;i++){
for(int j=init;j<init+subArrLen;j++){
targetArr[i][j] = queue.poll();
}
}
rowIdx+=subArrLen;
}
while(colIdx<targetArr.length-init-subArrLen){
for(int i=rowIdx;i<rowIdx+subArrLen;i++){
for(int j=colIdx;j<colIdx+subArrLen;j++){
targetArr[i][j] = queue.poll();
}
}
colIdx+=subArrLen;
}
while(rowIdx>init){
for(int i=rowIdx;i<rowIdx+subArrLen;i++){
for(int j=colIdx;j<colIdx+subArrLen;j++){
targetArr[i][j] = queue.poll();
}
}
rowIdx-=subArrLen;
}
rotateRight2(targetArr,l,init+subArrLen);
}
static void rotateLeft2(int[][] targetArr,int l,int init){
int subArrLen = (int)Math.pow(2,l);
if(subArrLen>targetArr.length){
return;
}
if(init>=targetArr.length/2){
return;
}
Queue<Integer> queue = new LinkedList<>();
//담기_각 배열 모양대로 담아야 함.
int rowIdx = init;
while(rowIdx< targetArr.length-init-subArrLen){
for(int i=rowIdx;i<rowIdx+subArrLen;i++){
for(int j=init;j<init+subArrLen;j++){
queue.offer(targetArr[i][j]);
}
}
rowIdx+=subArrLen;
}
int colIdx = init;
while(colIdx< targetArr.length-init-subArrLen){
for(int i=targetArr.length-subArrLen-init;i< targetArr.length-init;i++){
for(int j=colIdx;j<colIdx+subArrLen;j++){
queue.offer(targetArr[i][j]);
}
}
colIdx+=subArrLen;
}
while(rowIdx>init){
for(int i=rowIdx;i<rowIdx+subArrLen;i++){
for(int j=targetArr.length-init-subArrLen;j< targetArr.length-init;j++){
queue.offer(targetArr[i][j]); }
}
rowIdx-=subArrLen;
}
while(colIdx>init){
for(int i=init;i<init+subArrLen;i++){
for(int j=colIdx;j<colIdx+subArrLen;j++){
queue.offer(targetArr[i][j]);
}
}
colIdx-=subArrLen;
}
//미뤄서 채우기!
rowIdx = targetArr.length-init-subArrLen;
colIdx = init;
while(colIdx<targetArr.length-init-subArrLen){
for(int i=rowIdx;i<rowIdx+subArrLen;i++){
for(int j=colIdx;j<colIdx+subArrLen;j++){
targetArr[i][j] = queue.poll();
}
}
colIdx+=subArrLen;
//colIdx = targetArr.length-init-subArrLen
}
while(rowIdx>init){
for(int i=rowIdx;i<rowIdx+subArrLen;i++){
for(int j=colIdx;j<colIdx+subArrLen;j++){
targetArr[i][j] = queue.poll();
}
}
rowIdx-=subArrLen;
//rowIdx = init
}
while(colIdx>init){
for(int i=rowIdx;i<rowIdx+subArrLen;i++){
for(int j=colIdx;j<colIdx+subArrLen;j++){
targetArr[i][j] = queue.poll();
}
}
colIdx-=subArrLen;
//colIdx=init
}
while(rowIdx<targetArr.length-init-subArrLen){
for(int i=rowIdx;i<rowIdx+subArrLen;i++){
for(int j=colIdx;j<colIdx+subArrLen;j++){
targetArr[i][j] = queue.poll();
}
}
rowIdx+=subArrLen;
}
rotateLeft2(targetArr,l,init+subArrLen);
}
}
꽤 고생을 하면서 풀어서 여러 가지 느낀 점이 많다. 가장 절실히 느낀 것은, 구현 문제를 풀 때는 두려움을 느끼면 안 된다는 것이다. 사실 이 문제를 푸는 대부분의 시간은 배열을 돌리는 경우에서 "도대체 어디서부터 시작해서 어떻게 채워넣지?" 하는 것을 생각하는 데 소모되었다. 사실 내가 그걸 몰랐냐? 배열의 인덱스들을 다룰 줄 몰랐냐? 물어보면, 당연히 다룰 줄 알았다. 대부분의 시간은 내가 컴퓨터 앞에 앉아서 "아... 너무 오래 걸릴 거 같은데.. 다른 방법 없나?", "아... 생각하기 싫다..." 하는 생각을 하면서 지지부진하게 소모되었다. 그냥 보자마자 종이 한 장 펼쳐 놓고 그림 그려가며 풀었으면 금방 해냈을 듯 하다.
둘째는, 코드를 칠 때 반드시 주석을 다는 습관을 들여야 한다는 것이다. 내가 큐를 만들어 놓고 돌려 쓴 게 아니라 매 함수마다 새로 큐를 만들어 쓰는 등.. 코드 작성이 효율적이지 못하기에 487줄짜리 코드를 썼는데, 테케들을 돌리면서 중간중간 실수한 부분을 고칠 때나 잠시 생각이 막혔을 때 주석이 없어서 헤매면서 잡아먹은 시간도 만만치 않다. 특히, rowIdx, colIdx 등을 다룰 때 내가 내가 친 코드를 보면서 헷갈려하다가 '뇌정지'가 온 적이 많다.
셋째는, 이렇게 여러 단계를 거쳐서 답을 도출하는 문제의 경우에는, 테케를 돌릴 때 각 단계마다 출력해 가면서 확인해야 한다는 것이다. 이번 경우에도 내가 1,2 번을 잘못 쓴 것을 각 단계마다 출력하는 과정을 거치면서 캐치할 수 있었다.
흐뭇-
'프로그래밍 > 백준 복기' 카테고리의 다른 글
| [구현] 백준 20061: 모노미노도미노 2 (0) | 2022.07.27 |
|---|---|
| [구현] 백준 14503: 로봇 청소기 (0) | 2022.07.27 |
| [구현] 백준 16927: 배열 돌리기 2 (0) | 2022.07.20 |
| [DP] BOJ_14501: 퇴사 (0) | 2022.06.29 |
| [DP] BOJ_2133: 타일 채우기 (0) | 2022.06.29 |
