-
[2020 KAKAO BLIND RECRUITMENT] 자물쇠와 열쇠문제 풀이/KAKAO BLIND RECRUITMENT 2021. 1. 1. 15:35
[2020 KAKAO BLIND RECRUITMENT] 괄호 반환자물쇠와 열쇠
코딩테스트 연습 - 자물쇠와 열쇠
[[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true
programmers.co.kr
key 행렬을 돌리고 옮겨가며 모든 경우의 수를 시도해보는 문제이다. 우선 특정 행렬을 돌리는 메소드를 구현했다.
public class LockAndKey_1 { static int get(int[][] a, int rotation, int row, int col) { // 현재 위치를 넣고, 돌렸을 때 값이 들어 있는 위치의 값을 반환하는 메소드 if (rotation == 90) { int temp = row; row = a.length - 1 - col; col = temp; } else if (rotation == 180) { row = a.length - 1 - row; col = a.length - 1 - col; } else if (rotation == 270) { int temp = row; row = col; col = a.length - 1 - temp; } return a[row][col]; } static void print(int[][] a, int rotation) { for (int row = 0; row < a.length; row++) { for (int col = 0; col < a.length; col++) { System.out.printf("%2d", get(a, rotation, row, col)); // 90도 회전했을 때 (0, 0)을 get } System.out.println(); } System.out.println(); } public static void main(String[] args) { int[][] a = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; for (int rotation = 0; rotation < 360; rotation += 90) { print(a, rotation); } } }1 2 3 4 5 6 7 8 9 7 4 1 8 5 2 9 6 3 9 8 7 6 5 4 3 2 1 3 6 9 2 5 8 1 4 70, 90, 180, 270를 시계방향으로 돌렸을 때 회전 전의 좌표의 값을 반환하는 get 메소드이다.
7을 90도 돌렸을 때, (2, 0)에서 (0, 0)으로 와야한다. (0, 2) -> (0, 0)
8은 90도 돌렸을 때, (2, 1)에서 (1, 2)로 와야한다. (2, 1) -> (1, 2)
5를 90도 돌렸을 때, (1, 1)에서 (1, 1)로 와야한다. (1, 1) -> (1, 1)
회전각이 90도 인 경우, 회전 후의 좌표 (row, col)의 값을 구하기 위하기 위한 회전 전 좌표는 (colLength - 1 - col, col) 이 된다. 이것을 코드로 바꾸면,
int temp = row; row = a.length - 1 - col; col = temp;회전각이 180도 인 경우, 회전 후의 좌표 (row, col)의 값을 구하기 위한 회전 전 좌표는 (rowLength - 1 - row, colLength - 1 - col)이 된다. 이것을 코드로 바꾸면,
row = a.length - 1 - row; col = a.length - 1 - col;회전각이 270도 인 경우, 회전 후의 좌표 (row, col)의 값을 구하기 위한 회전 전 좌표는 (col, rowLength - 1 - row)가 된다. 이것을 코드로 바꾸면,
int temp = row; row = col; col = a.length - 1 - temp;
이제 돌린 좌표의 값을 구하는 메소드는 완료 하였고, 행렬 이동에 대한 좌표를 구현하였다. 이제는 돌리기 전, 이동하기 전에 어떤 좌표의 값인지를 계산하는 역할이다.
예를 들어
오른쪽으로 2칸, 아래로 1칸 이동한 후 좌표가 (row, col)이면, 이동 전 좌표는 (row - 2. col - 1)이 된다.
90도 회전한 후 오른쪽으로 2칸, 아래로 1칸 이동한 좌표가 (row, col)이면, 이동 전 좌표는 (colLength - 1 - (col - 1), (row - 2)) 이 된다. 이것을 앞서 만든 get메소드에 적용한다.
public class LockAndKey_2 { static int get(int[][] a, int rotation, int rowMove, int colMove, int row, int col) { row -= rowMove; col -= colMove; if (row < 0 || a.length - 1 < row) return 0; // 범위를 넘어가면 if (col < 0 || a.length - 1 < col) return 0; // 범위를 넘어가면 if (rotation == 90) { int temp = row; row = a.length - 1 - col; col = temp; } else if (rotation == 180) { row = a.length - 1 - row; col = a.length - 1 - col; } else if (rotation == 270) { int temp = row; row = col; col = a.length - 1 - temp; } return a[row][col]; } static void print(int[][] key, int rotation, int rowMove, int colMove) { for (int row = -2; row < key.length + 2; row++) { for (int col = -2; col < key.length + 2; col++) { int k = get(key, rotation, rowMove, colMove, row, col); System.out.printf("%2s", k > 0 ? String.valueOf(k) : "."); } System.out.println(); } System.out.println(); } public static void main(String[] args) { int[][] a = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; for (int rotation = 0; rotation < 360; rotation += 90) { System.out.println("--------------------"); for (int move = -a.length + 1; move < a.length; move++) { print(a, rotation, move, move); } } } }-------------------- 1 2 3 . . . . 4 5 6 . . . . 7 8 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 3 . . . . 4 5 6 . . . . 7 8 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 3 . . . . 4 5 6 . . . . 7 8 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 3 . . . . 4 5 6 . . . . 7 8 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 3 . . . . 4 5 6 . . . . 7 8 9 -------------------- 7 4 1 . . . . 8 5 2 . . . . 9 6 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4 1 . . . . 8 5 2 . . . . 9 6 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4 1 . . . . 8 5 2 . . . . 9 6 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4 1 . . . . 8 5 2 . . . . 9 6 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4 1 . . . . 8 5 2 . . . . 9 6 3 -------------------- 9 8 7 . . . . 6 5 4 . . . . 3 2 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 8 7 . . . . 6 5 4 . . . . 3 2 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 8 7 . . . . 6 5 4 . . . . 3 2 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 8 7 . . . . 6 5 4 . . . . 3 2 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 8 7 . . . . 6 5 4 . . . . 3 2 1 -------------------- 3 6 9 . . . . 2 5 8 . . . . 1 4 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 6 9 . . . . 2 5 8 . . . . 1 4 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 6 9 . . . . 2 5 8 . . . . 1 4 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 6 9 . . . . 2 5 8 . . . . 1 4 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 6 9 . . . . 2 5 8 . . . . 1 4 7이전과 달라진 부분은 get 메소드에서 이동한 값인 rowMove와 colMove를 우선적으로 빼준다. 그 다음 해당 범위가 넘어가면 값을 넣을 수 없으므로 0으로 반환한다. 이동하는 과정을 보이기 위해 행렬의 크기를 임시로 6 x 6로 만들었다. 의도한 대로 돌리고 움직이는 것을 알 수 있다.
이제 앞서 만든 메소드를 활용하여 solution을 해결해보자.
public class LockAndKey_solution { static int getKey(int[][] key, int rotation, int rowMove, int colMove, int row, int col) { row -= rowMove; col -= colMove; if (row < 0 || key.length - 1 < row) return 0; if (col < 0 || key.length - 1 < col) return 0; if (rotation == 90) { int temp = row; row = key.length - 1 - col; col = temp; } else if (rotation == 180) { row = key.length - 1 - row; col = key.length - 1 - col; } else if (rotation == 270) { int temp = row; row = col; col = key.length - 1 - temp; } return key[row][col]; } static boolean isKey(int[][] lock, int[][] key, int rotation, int rowMove, int colMove) { for (int row = 0; row < lock.length; row++) { for (int col = 0; col < lock.length; col++) { if (getKey(key, rotation, rowMove, colMove, row, col) == lock[row][col]) return false; } } return true; } public static boolean solution(int[][] key, int[][] lock) { for (int rotation = 0; rotation < 360; rotation += 90) { for (int rowMove = -(key.length - 1); rowMove < lock.length; rowMove++) { for (int colMove = -(key.length - 1); colMove < lock.length; colMove++) { if (isKey(lock, key, rotation, rowMove, colMove)) return true; } } } return false; } public static void main(String[] args) { int[][] key = {{0, 0, 0}, {1, 0, 0}, {0, 1, 1}}; int[][] lock = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}}; System.out.println(solution(key, lock)); } }truegetKey() key를 돌리고 움직이기 전에 좌표의 값을 구하는 메소드이다.
static int getKey(int[][] key, int rotation, int rowMove, int colMove, int row, int col) { row -= rowMove; col -= colMove; if (row < 0 || key.length - 1 < row) return 0; if (col < 0 || key.length - 1 < col) return 0; if (rotation == 90) { int temp = row; row = key.length - 1 - col; col = temp; } else if (rotation == 180) { row = key.length - 1 - row; col = key.length - 1 - col; } else if (rotation == 270) { int temp = row; row = col; col = key.length - 1 - temp; } return key[row][col]; }isKey()는 getKey로 얻은 값을 lock과 비교하여 key가 들어갈 홈이 전부 비어있으면 ture를 반환한다. 하지만 하나라도 맞지 않으면 false를 반환한다.
static boolean isKey(int[][] lock, int[][] key, int rotation, int rowMove, int colMove) { for (int row = 0; row < lock.length; row++) { for (int col = 0; col < lock.length; col++) { if (getKey(key, rotation, rowMove, colMove, row, col) == lock[row][col]) return false; } } return true; }마지막으로 solution이다.
public static boolean solution(int[][] key, int[][] lock) { for (int rotation = 0; rotation < 360; rotation += 90) { for (int rowMove = -(key.length - 1); rowMove < lock.length; rowMove++) { for (int colMove = -(key.length - 1); colMove < lock.length; colMove++) { if (isKey(lock, key, rotation, rowMove, colMove)) return true; } } } return false; }회전각도를 돌려가며 lock 배열의 크기에 맞추어 이동하며 lock에 key가 맞을 때 까지 돌린다. 맞는 즉시 값을 반환해준다.
references.
소프트웨어공학과 이승진 교수님의 특강자료를 기반으로 작성된 게시글입니다.
'문제 풀이 > KAKAO BLIND RECRUITMENT' 카테고리의 다른 글
[2020 KAKAO BLIND RECRUITMENT] 가사 검색 (0) 2021.01.10 [2020 KAKAO BLIND RECRUITMENT] 괄호 반환 (0) 2020.12.29 [2020 KAKAO BLIND RECRUITMENT] 문자열 압축 (0) 2020.12.29