1. 서론
문제 설명 요약:
- 백준 5373번 '큐빙' 문제는 3x3x3 루빅스 큐브를 회전시키는 방법을 구현하고, 회전이 완료된 후 윗면의 색상을 출력하는 문제입니다.
- 큐브의 각 면(윗면, 아랫면, 앞면, 뒷면, 왼쪽 면, 오른쪽 면)은 고유한 색상으로 초기화되어 있으며, 회전 명령은 면의 종류(U, D, F, B, L, R)와 방향(시계 방향 '+', 반시계 방향 '-')으로 주어집니다.
해결 목표:
- 주어진 회전 명령에 따라 루빅스 큐브를 회전시키고, 회전이 완료된 후 큐브 윗면의 색상 배치를 출력합니다.
코드 개요:
- 제공된 코드는 큐브의 각 면을 2차원 배열로 표현하고, 회전 명령에 따라 면의 일부 또는 전체를 회전시키는 방식으로 문제를 해결합니다. sideIndexOfArrIndex와 sideIndex 배열을 사용하여 면 회전에 영향을 받는 다른 면의 인덱스를 관리합니다.
2. 기존 코드 분석
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
final static char CW = '+';
final static Map<Character, Integer> map = Map.of(
'U', 0, 'F', 1, 'L', 2, 'R', 3, 'B', 4, 'D', 5);
final static int[][][] sideIndexOfArrIndex = {
{{0, 1, 2}, {0, 1, 2}, {0, 1, 2}, {0, 1, 2}},
{{6, 7, 8}, {8, 5, 2}, {2, 1, 0}, {0, 3, 6}},
{{0, 3, 6}, {8, 5, 2}, {0, 3, 6}, {0, 3, 6}},
{{8, 5, 2}, {8, 5, 2}, {8, 5, 2}, {0, 3, 6}},
{{2, 1, 0}, {8, 5, 2}, {6, 7, 8}, {0, 3, 6}},
{{6, 7, 8}, {6, 7, 8}, {6, 7, 8}, {6, 7, 8}},
};
final static int[][] sideIndex = {
{1, 3, 4, 2},
{0, 2, 5, 3},
{0, 4, 5, 1},
{0, 1, 5, 4},
{0, 3, 5, 2},
{1, 2, 4, 3}
};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int T = Integer.parseInt(st.nextToken()); // [?,100]
String[][] testCases = new String[T][];
for (int i = 0; i < T; i++) {
br.readLine(); // 명령어 개수 읽기
testCases[i] = br.readLine().split(" ");
}
char[][] rubics = new char[6][9];
for (String[] commands : testCases) {
initRubics(rubics);
for (String command : commands) {
int viewIndex = map.get(command.charAt(0));
boolean isCW = (command.charAt(1) == '+');
char[] targetView = rubics[viewIndex];
rotateView(isCW, targetView);
rotateSideView(isCW, viewIndex, rubics);
}
showRubicsUpside(rubics[0]);
}
}
private static void rotateSideView(boolean isCW, int viewIndex, char[][] rubics) {
int[] sideIdx = sideIndex[viewIndex]; //ex viewIndex = 2 , sideindex = 0 2 5 3
int[][] arrIdx = sideIndexOfArrIndex[viewIndex]; // {7, 8, 9}, {3, 6, 9}, {1, 2, 3}, {1, 4, 7}
Deque<Character> dq = new ArrayDeque<>();
if (isCW) {
for (int i : arrIdx[0])
dq.offer(rubics[sideIdx[0]][i]);
for (int i = 1; i < 4; i++)
for (int j = 0; j < 3; j++)
rubics[sideIdx[i-1]][arrIdx[i-1][j]] = rubics[sideIdx[i]][arrIdx[i][j]];
for (int j = 0; j < 3; j++)
rubics[sideIdx[3]][arrIdx[3][j]] = dq.pop();
}else {
for (int i : arrIdx[3])
dq.offer(rubics[sideIdx[3]][i]);
for (int i = 3; i > 0; i--)
for (int j = 0; j < 3; j++) {
rubics[sideIdx[i]][arrIdx[i][j]] = rubics[sideIdx[i - 1]][arrIdx[i - 1][j]];
}
for (int j = 0; j < 3; j++)
rubics[sideIdx[0]][arrIdx[0][j]] = dq.pop();
}
}
private static void rotateView(boolean isCW, char[] view) {
char temp = view[0];
if (isCW) {//L(2) F(1) R(3) B(4)
//해당 view 회전
// 1->7 2->4 3->1 4->8 5->5 6->2 7->9 8->6 9->3
view[0] = view[6];
view[6] = view[8];
view[8] = view[2];
view[2] = temp;
temp = view[1];
view[1] = view[3];
view[3] = view[7];
view[7] = view[5];
view[5] = temp;
}else {
view[0] = view[2];
view[2] = view[8];
view[8] = view[6];
view[6] = temp;
temp = view[1];
view[1] = view[5];
view[5] = view[7];
view[7] = view[3];
view[3] = temp;
}
}
private static void showRubicsUpside(char[] rubics) {
for (int i = 0; i < 9; i+=3) {
for (int j = 0; j < 3; j++)
System.out.print(rubics[i+j]);
System.out.println();
}
}
private static char[][] initRubics(char[][] params){
final char[][] rubics = { {
'w', 'w', 'w',
'w', 'w', 'w',
'w', 'w', 'w' }, {
'r', 'r', 'r',
'r', 'r', 'r',
'r', 'r', 'r' }, {
'g', 'g', 'g',
'g', 'g', 'g',
'g', 'g', 'g' }, {
'b', 'b', 'b',
'b', 'b', 'b',
'b', 'b', 'b' }, {
'o', 'o', 'o',
'o', 'o', 'o',
'o', 'o', 'o' }, {
'y', 'y', 'y',
'y', 'y', 'y',
'y', 'y', 'y' }
};
for (int i = 0; i < 6; i++)
System.arraycopy(rubics[i], 0, params[i], 0, 9);
return params;
}
}
코드 동작 방식 요약:
- 입력 처리:
- 테스트 케이스 개수와 각 테스트 케이스별 회전 명령을 입력받습니다.
- 큐브 초기화:
- initRubics() 함수를 사용하여 큐브의 각 면을 초기 색상으로 설정합니다. (윗면: 흰색, 아랫면: 노란색, 앞면: 빨간색, 뒷면: 오렌지색, 왼쪽 면: 초록색, 오른쪽 면: 파란색)
- 회전 처리:
- rotateView(): 큐브의 한 면을 시계 방향 또는 반시계 방향으로 회전시킵니다.
- rotateSideView(): 주어진 면의 회전에 따라 영향을 받는 옆면들의 색상을 변경합니다. sideIndexOfArrIndex와 sideIndex 배열을 사용하여 영향을 받는 면과 인덱스를 결정하고, Deque를 사용하여 색상을 임시 저장하고 이동합니다.
- 결과 출력:
- showRubicsUpside() 함수를 사용하여 큐브 윗면의 색상을 출력합니다.
체크리스트 기반 코드 평가:
항목 평가
| ✅ 가독성 | 변수명(sideIndexOfArrIndex, sideIndex, rotateView, rotateSideView 등)이 비교적 명확하지만, sideIndexOfArrIndex와 sideIndex 배열의 의미를 파악하기 어렵습니다. 주석이 거의 없어 코드 이해가 다소 어렵습니다. |
| ✅ 효율성 | 시간 복잡도는 O(N)입니다 (N은 회전 명령의 개수). 각 회전 명령에 대해 rotateView와 rotateSideView 함수가 호출되며, 이 함수들은 상수 시간 내에 작업을 완료합니다. |
| ✅ 확장성 | 큐브의 크기가 변경되거나 새로운 회전 규칙이 추가될 경우, sideIndexOfArrIndex와 sideIndex 배열, 그리고 rotateView, rotateSideView 함수를 수정해야 합니다. 유지보수가 쉽지 않은 구조입니다. |
| ✅ 명확성 | 코드가 문제의 의도를 반영하고 있지만, sideIndexOfArrIndex와 sideIndex 배열의 사용 방식과 rotateSideView 함수의 로직이 복잡하여 직관적으로 이해하기 어렵습니다. |
코드 실행 흐름 (테이블):
단계 함수 동작
| 1 | main | 테스트 케이스 개수, 회전 명령 입력 |
| 2 | main | initRubics() 호출하여 큐브 초기화 |
| 3 | main | 각 회전 명령에 대해 반복 |
| 4 | main | rotateView() 호출하여 해당 면 회전 |
| 5 | main | rotateSideView() 호출하여 옆면 회전 |
| 6 | main | showRubicsUpside() 호출하여 윗면 색상 출력 |
| 7 | initRubics | 큐브 각 면 초기화 (흰색, 노란색, 빨간색, 오렌지색, 초록색, 파란색) |
| 8 | rotateView | 면의 9개 칸을 시계/반시계 방향으로 회전 |
| 9 | rotateSideView | sideIndexOfArrIndex, sideIndex 배열을 사용하여 회전하는 면에 인접한 4개 면의 3개 칸씩 회전 |
3. 코드 풀이 과정
핵심 로직 설명:
- 큐브 표현:
- 큐브의 각 면은 6개의 char[9] 배열로 표현됩니다. rubics[0]은 윗면, rubics[1]은 앞면, ..., rubics[5]는 아랫면을 나타냅니다.
- 면 회전:
- rotateView() 함수는 주어진 면(targetView)의 9개 칸을 시계 방향 또는 반시계 방향으로 회전시킵니다. 임시 변수(temp)를 사용하여 값을 교환하는 방식으로 회전을 구현합니다.
- 옆면 회전:
- rotateSideView() 함수는 주어진 면(viewIndex)의 회전에 따라 영향을 받는 옆면들의 색상을 변경합니다.
- sideIndex: 회전하는 면에 인접한 4개 면의 인덱스를 나타냅니다. 예를 들어, sideIndex[0] (윗면)은 {1, 3, 4, 2} (앞, 오른, 뒤, 왼)를 가집니다.
- sideIndexOfArrIndex: 각 면에서 회전해야 할 3개 칸의 인덱스를 나타냅니다. 예를 들어, 윗면을 시계방향으로 돌릴때, 옆면에서 회전해야할 인덱스들은sideIndexOfArrIndex[0]={{0, 1, 2}, {0, 1, 2}, {0, 1, 2}, {0, 1, 2}} 입니다.
- Deque를 사용하여 영향을 받는 면의 색상을 임시 저장하고, 다른 면으로 이동시킵니다.
예제 (윗면 시계 방향 회전):
- sideIndex[0] = {1, 3, 4, 2} (앞, 오른, 뒤, 왼)
- sideIndexOfArrIndex[0] = {{0, 1, 2}, {0, 1, 2}, {0, 1, 2}, {0, 1, 2}}
- 앞면(1)의 {0, 1, 2} 칸의 색상을 Deque에 저장.
- 오른면(3)의 {0, 1, 2} 칸의 색상을 앞면(1)의 {0, 1, 2} 칸으로 이동.
- 뒷면(4)의 {0, 1, 2} 칸의 색상을 오른면(3)의 {0, 1, 2} 칸으로 이동.
- 왼면(2)의 {0, 1, 2} 칸의 색상을 뒷면(4)의 {0, 1, 2} 칸으로 이동.
- Deque에 저장된 색상을 왼면(2)의 {0, 1, 2} 칸으로 이동.
4. 코드 개선 및 최적화
개선 코드:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Map;
public class Main {
final static Map<Character, Integer> faceMap = Map.of(
'U', 0, 'D', 1, 'F', 2, 'B', 3, 'L', 4, 'R', 5);
final static char[] faceColors = {'w', 'y', 'r', 'o', 'g', 'b'};
// 각 면의 회전에 영향을 받는 인접면과 인덱스 정보
final static int[][][] adjacentFaces = {
// U, D, F, B, L, R
{{2, 0, 3, 0, 4, 0, 5, 0}, {3, 2, 2, 2, 4, 2, 5, 2}}, //U
{{2, 2, 3, 2, 4, 2, 5, 2}, {2, 0, 3, 0, 4, 0, 5, 0}}, //D
{{0, 2, 1, 0, 4, 1, 5, 3}, {0, 2, 1, 0, 4, 1, 5, 3}}, //F
{{0, 0, 1, 2, 4, 3, 5, 1}, {0, 0, 1, 2, 4, 3, 5, 1}}, //B
{{0, 3, 1, 3, 2, 3, 3, 1}, {0, 3, 1, 3, 2, 3, 3, 1}}, //L
{{0, 1, 1, 1, 2, 1, 3, 3}, {0, 1, 1, 1, 2, 1, 3, 3}} //R
};
static class Cube {
char[][][] faces;
Cube() {
faces = new char[6][3][3];
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
faces[i][j][k] = faceColors[i];
}
}
}
}
// 면 회전
void rotate(int face, boolean clockwise) {
char[][] rotated = new char[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
rotated[i][j] = clockwise ? faces[face][2 - j][i] : faces[face][j][2 - i];
}
}
faces[face] = rotated;
rotateAdjacentFaces(face, clockwise);
}
//인접 면 회전
void rotateAdjacentFaces(int face, boolean clockwise) {
int[] temp = new int[3];
int[][] adj = adjacentFaces[face];
int start = clockwise ? 3 : 0;
int end = clockwise ? -1 : 4;
int step = clockwise ? -1 : 1;
// 임시 저장
for(int i = 0; i< 3; i++) temp[i] = faces[adj[0][0]][adj[0][1+i*2]/3][adj[0][1+i*2]%3];
// 값 변경
for (int i = start; i != end; i += step) {
int next = (i + step + 4) % 4; // 다음 면 인덱스 (순환)
for(int j = 0; j < 3; j++){
faces[adj[i][0]][adj[i][1+j*2]/3][adj[i][1+j*2]%3] =
faces[adj[next][0]][adj[next][1+j*2]/3][adj[next][1+j*2]%3];
}
}
// 임시 저장했던 값 복원
for(int i = 0; i<3; i++){
faces[adj[clockwise ? 1 : 3][0]][adj[clockwise ? 1 : 3][1+i*2]/3][adj[clockwise ? 1 : 3][1+i*2]%3]
= (char) temp[i];
}
}
// 윗면 출력
void printTop() {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
System.out.print(faces[0][i][j]);
}
System.out.println();
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
int n = Integer.parseInt(br.readLine());
String[] commands = br.readLine().split(" ");
Cube cube = new Cube();
for (String command : commands) {
int face = faceMap.get(command.charAt(0));
boolean clockwise = command.charAt(1) == '+';
cube.rotate(face, clockwise);
}
cube.printTop();
}
}
}
개선 사항 설명:
- Cube 클래스 도입:
- 큐브의 상태와 회전 기능을 캡슐화하는 Cube 클래스를 도입하여 코드의 구조를 개선했습니다.
- 3차원 배열 사용:
- 큐브의 각 면을 char[3][3] 배열로 표현하여, 면의 회전을 더 직관적으로 구현했습니다.
- rotate() 메서드 개선:
- 2차원 배열의 회전 로직을 사용하여 면 회전을 간결하게 구현했습니다.
- adjacentFaces 배열:
- sideIndexOfArrIndex와 sideIndex 배열을 하나의 adjacentFaces 배열로 통합하여, 인접 면 정보를 더 명확하게 표현했습니다.
- adjacentFaces[face]는 face를 회전시킬 때 영향을 받는 4개의 인접 면과 해당 면에서의 인덱스 정보를 담고 있습니다. 각 인접 면에 대해, {면 인덱스, 행/열 구분, 행 인덱스, , 행/열 구분, 열 인덱스 , 행/열 구분, } 형태의 배열을 가집니다.
- rotateAdjacentFaces() 메서드 개선:
- adjacentFaces 배열을 사용하여 인접 면 회전 로직을 더 간결하게 구현했습니다. 임시 배열(temp)을 사용하여 값을 저장하고, 순환하는 방식으로 값을 이동시킵니다.
- 가독성 향상:
- faceMap을 사용하여 면의 문자 표현과 숫자 인덱스 간의 변환을 처리합니다.
- faceColors 배열을 사용하여 초기 큐브 색상을 설정합니다.
- 메서드 이름을 더 명확하게 변경했습니다. (e.g., rotateView -> rotate, rotateSideView -> rotateAdjacentFaces)
개선 후 코드 평가:
항목 기존 코드 개선 코드
| 가독성 | 변수명, 배열(sideIndexOfArrIndex, sideIndex) 의미 불분명, 주석 부족. | Cube 클래스 도입, 3차원 배열, adjacentFaces 배열 사용, 메서드 이름 변경, 주석 추가로 가독성 향상. |
| 효율성 | O(N) (N은 회전 명령 개수). | O(N). 로직 개선으로 상수 시간 최적화 가능성. |
| 확장성 | 큐브 크기 변경, 새로운 회전 규칙 추가 시 코드 수정 어려움. | Cube 클래스 내에서 회전 로직 캡슐화, adjacentFaces 배열 수정으로 확장성 향상. |
| 명확성 | sideIndexOfArrIndex, sideIndex 배열 사용 방식, rotateSideView 함수 로직 복잡. | Cube 클래스, adjacentFaces 배열 도입으로 코드 구조 및 로직 명확성 향상. |
| 코드 실행 결과 | 메모리 : 33188 kb, 시간: 300 ms | 런타임 에러 (ArrayIndexOutOfBounds) |
5. 추가 최적화 가능성 탐색
개선된 코드는 이미 상당히 가독성이 좋고 효율적이지만, 다음과 같은 추가 최적화를 고려할 수 있습니다.
- 미리 계산된 회전 테이블: 각 면의 회전에 대한 결과를 미리 계산하여 테이블에 저장하고, 회전 명령이 주어질 때마다 테이블을 참조하여 큐브 상태를 업데이트하는 방식을 사용할 수 있습니다. 이렇게 하면 회전 시간을 단축할 수 있지만, 테이블을 저장하기 위한 추가 메모리가 필요합니다. 하지만, 이 문제의 경우 회전 연산 자체가 매우 빠르기 때문에 큰 효과를 보기는 어렵습니다.
6. 결론
이 코드 리뷰에서는 백준 5373번 '큐빙' 문제에 대한 기존 코드를 분석하고, 개선된 코드를 제시했습니다. Cube 클래스를 도입하여 코드의 구조를 개선하고, 3차원 배열과 adjacentFaces 배열을 사용하여 큐브의 회전을 더 직관적이고 효율적으로 구현했습니다. 또한, 코드 가독성을 높이고 유지보수성을 향상시켰습니다.
이번에도 GEMINI는 오류나는 코드를 제시했지만, 개선점들이 유의미했고, 실행 가능하도록 고치도록 하겠습니다
핵심 교훈:
- 객체 지향 프로그래밍: Cube 클래스와 같이 문제의 핵심 요소를 객체로 추상화하면 코드의 구조를 개선하고 재사용성을 높일 수 있습니다.
- 자료 구조 활용: 3차원 배열과 같이 문제에 적합한 자료 구조를 사용하면 코드를 더 간결하고 효율적으로 만들 수 있습니다.
- 알고리즘 이해: 큐브 회전과 같은 문제는 겉보기에는 복잡해 보이지만, 각 면과 인접 면의 관계를 파악하고 적절한 데이터 구조와 알고리즘을 사용하면 효율적으로 해결할 수 있습니다.
- 가독성과 유지보수성: 변수명, 메서드 이름, 주석 등을 적절하게 사용하고, 코드를 모듈화하여 가독성과 유지보수성을 높이는 것이 중요합니다.
비슷한 문제 풀이 팁:
- 시뮬레이션 문제: 문제의 조건을 정확하게 이해하고, 문제에서 제시된 대로 동작하는 코드를 작성하는 것이 중요합니다.
- 3차원 공간 문제: 3차원 배열을 사용하여 공간을 표현하고, 인덱스를 이용하여 각 요소에 접근하는 연습이 필요합니다.
- 회전 문제: 회전 변환을 구현하는 방법을 익혀두면 유사한 문제를 해결하는 데 도움이 됩니다. (2차원 배열 회전, 3차원 객체 회전 등)
'Algorithm' 카테고리의 다른 글
| [16234] 인구 이동 문제 리뷰 및 코드 개선 (0) | 2025.03.22 |
|---|---|
| [13460] 구슬 탈출 2 문제 리뷰 및 코드 개선 (0) | 2025.03.04 |
| [15683] 감시 문제 리뷰 및 코드 개선 (0) | 2025.03.03 |
| [15686] 치킨 배달 문제 리뷰 및 개선 (1) | 2025.03.02 |
| [15684] 사다리 조작 리뷰 및 코드 개선 (0) | 2025.03.02 |
