코딩 테스트를 준비할때 알아두면 시험볼때 편리 할 코드들을 정리하겠습니다.
1. 행렬의 순환
여기서 포스팅하려는 행렬의 순환은 N x M 행렬이 주어지고,
아래 그림과 같이 한 방향으로 순환을 하는 코드를 말합니다.
그림으로 예를 보자면
1) 코드를 한 번 실행하면 아래 그림과 같이 (1,2)에 있는 동그라미가 (1,3)으로 이동
2) 한번 더 실행하면 (1,3)에 있는 동그라미가 (2,3)으로 이동
3) 이것을 반복하면 행렬의 가장자리를 순환하게 됩니다.
이와 같은 행렬의 순환 코드를 정리 해보도록 하겠습니다.
2. 가장자리를 한칸 씩 이동하기
여기서 구현해 볼 코드는 그림 1 -> 그림 2 에서 볼때 처럼 (1,2)에 있는 동그라미를 삭제하고
(1,3)에 입력 해서 한번만 수행하는 것이 아닌,
아예 한번 실행하면 (1,1) 부터 가장자리만 한 칸씩 이동하도록 구현해 보겠습니다!!
그림으로 보자면 아래와 같습니다.
1) 한바퀴 돌면 아래 그림과 같이 가장자리를 1칸씩 이동합니다.
2) 한바퀴 더 돌면 아래 그림과 같아집니다.
3. 코드로 구현하기
이제 코드로 구현해보겠습니다.
package codingTest_concept;
public class Matrix_circulation {
public void circulation(String[][] matrix) {
int start_h = 0;
int start_w = 0;
String temp_1 = matrix[start_h][start_w];
String temp_2 = "";
//오른쪽 이동
while(start_w != matrix.length-1) {
temp_2 = matrix[start_h][start_w+1];
matrix[start_h][start_w+1] = temp_1;
temp_1 = temp_2;
start_w = start_w+1;
}
//아래로 이동
while(start_h != matrix.length-1) {
temp_2 = matrix[start_h+1][start_w];
matrix[start_h+1][start_w] = temp_1;
temp_1 = temp_2;
start_h = start_h+1;
}
//왼쪽으로 이동
while(start_w != 0) {
temp_2 = matrix[start_h][start_w-1];
matrix[start_h][start_w-1] = temp_1;
temp_1 = temp_2;
start_w = start_w-1;
}
//위로 이동
while(start_h != 0) {
temp_2 = matrix[start_h-1][start_w];
matrix[start_h-1][start_w] = temp_1;
temp_1 = temp_2;
start_h = start_h-1;
}
//출력
for(int i=0; i<matrix.length; i++) {
for(int j = 0; j<matrix[i].length; j++ ) {
System.out.print(matrix[i][j]+" ");
}
System.out.println();
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Matrix_circulation m = new Matrix_circulation();
String[][] matrix = {{"A","B","C"},{"H"," ","D"},{"G","F","E"}};
m.circulation(matrix);
System.out.println();
m.circulation(matrix);
}
}
4. 코드 설명
코드가 어떻게 돌아가는건지 그림으로 정리해보져
1. 첫번째로 temp_1, tmep_2를 생성한 후, temp_1에는 시작 위치의 값을 저장합니다.
그리고 오른쪽 이동 while문으로 진입합니다. 그리고 temp_2에 그 오른쪽 위치의 값을 저장합니다.
2. 그 다음 temp_1에 저장된 값을 오른쪽 위치에 저장하고, 현재 위치를 한칸 이동합니다.
(여기까지가 while문 오른쪽 이동 1바퀴 입니다.)
3. 다시 1번 부터 반복하게 됩니다.
1)temp_2에 현위치 기준 오른쪽 값을 저장하고,
2)오른쪽 위치에 temp_1에 저장된 값을 삽입합니다.
3) temp_1에 temp_2 값을 저장합니다.
4)그리고 현재 위치를 오른쪽으로 +1 하여 이동시킵니다.
5) 현재 위치가 행렬크기와 같아짐으로 while문을 빠져나옵니다.
- while문 아래쪽
오른쪽 이동이 완료되었으니, 아래쪽으로 이동 while문을 시작합니다.
1) temp_2에 현 위치 기준 아래쪽 위치의 값을 저장합니다.
2) temp_1에 저장되어있던 값을 아래쪽 위치에 저장합니다.
3) 그리고 아래 그림과 같이 현재 위치를 아래로 한 칸 이동합니다.
(이렇게 하면 아래쪽 while문 한바퀴를 돌게 됩니다.)
그림 9, 그림 10 과정을 아래쪽 위치가 행렬의 h 크기와 동일해질때까지 반복합니다.
이렇게 되면 현재 위치와 행렬의 h값과 동일해짐으로 while문을 빠져나옵니다.
그 다음은 왼쪽 이동 while로 진입하게 됩니다.
왼쪽 이동은 오른쪽 이동 반대로, 위쪽 이동은 아래쪽 이동 반대로 진행되기에 그림은 생략하겠습니다.(귀찮은거 아님)
왼쪽이동 while을 끝내고 위쪽이동 while을 끝내면 아래 그림과 같이 마무리가 됩니다!
이렇게 메서드를 실행하면 한바퀴를 돌게 되는 것이죠!
움직이는 미로 탈출이나, 광고판 시뮬레이션 문제를 풀게될때, 이용하면 좋을 것 같아 정리해보았습니다.
while문의 순서를 바꾸면 반 시계방향으로 돌릴 수 있고, 한번 실행 시 2칸씩 이동한다는 조건이 있으면, 위 메서드를 2번 실행시키면 됩니다.
물론, 효율성 문제를 따지는 문제라면 다른 방식을(?) 찾아봐야겠지만요.
'알고리즘 공부 > 코딩테스트 준비' 카테고리의 다른 글
| DFS/BFS 탐색 알고리즘 (행렬 구현) (0) | 2019.06.03 |
|---|---|
| 진수 변환 (0) | 2019.05.20 |
| 피보나치 수열 (0) | 2019.05.20 |