(2021카카오) 카드 짝 맞추기 Java

풀이

키 조작 횟수가 가장 적은 방법

https://programmers.co.kr/learn/courses/30/lessons/72415

 

정답률 0.95%인 문제이다. 극악의 문제였으니, 너무 부담갖지는말되, 이런문제까지 풀 수있어야 카카오 개발자가 된다는 마음가짐으로 공부하자. 2021년 카카오 신입공채 1차 6번 문제였다.

 

조합에 관한 내용 , DFS, BFS에 관핸 내용은 확실하게 숙지해야겠다.

 

풀이

---

카카오 풀이 : tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

 

 

카드 종류가 최대 6개이므로, 어떤 카드부터 제거해 나갈지 정하는 방법은 6! 가지입니다. 예를 들어 카드가 3종류인 경우, 3종류 카드를 제거하는 순서는 다음과 같이 6가지입니다.  => Permutation 사용

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

위와 같이 카드를 제거하는 모든 순서에 대해서 각각 카드를 제거해 보고, 그중 키 조작 횟수가 가장 적은 방법을 찾으면 됩니다. 이때, 각 카드는 종류별로 2장씩이므로, 두 카드를 제거하는 순서에 따라 키 조작 횟수가 달라질 수 있음을 주의합니다. 즉, 현재 제거해야 되는 카드 번호 X에 대해서, 카드 하나를 XA, 다른 카드 하나를 XB라고 했을 때 다음 두 가지 경우에 대해 고려해 주면 됩니다. =>

• 현재 커서 위치 → XA 카드를 제거 → XB 카드를 제거
• 현재 커서 위치 → XB 카드를 제거 → XA 카드를 제거

만약 XB 카드를 나중에 제거했고, X 카드 다음으로 Y 카드를 제거해야 한다면 이번에는 다음과 같이 두 가지 경우를 고려합니다.

• 현재 커서 위치(XB 카드 위치) → YA 카드를 제거 → YB 카드를 제거
• 현재 커서 위치(XB 카드 위치) → YB 카드를 제거 → YA 카드를 제거

따라서 위와 같은 방법으로 카드를 제거하는 가능한 모든 방법을 고려해 주면 되며, “현재 커서 위치 → XA 카드를 제거”와 같이 커서를 이동시키는 최소 조작 횟수는 BFS 탐색을 이용하여 최단거리를 구하면 됩니다.

 

 

 

import java.util.*;

class Solution {
​​​​ArrayList<int[]> orders;
​​​​int[] dr = {1, -1, 0, 0};
​​​​int[] dc = {0, 0, 1, -1};

​​​​public int solution(int[][] board, int r, int c) {
​​​​​​​​int answer = Integer.MAX_VALUE;
​​​​​​​​int n = 0;
​​​​​​​​for (int[] row : board) {//개수세기
​​​​​​​​​​​​for (int e : row) {
​​​​​​​​​​​​​​​​if (e != 0) n++;
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​n /= 2;//짝 개수
​​​​​​​​int[] temp = new int[n];//12345...n
​​​​​​​​for (int i = 0; i < n; i++) {
​​​​​​​​​​​​temp[i] = i + 1;
​​​​​​​​}
​​​​​​​​orders = new ArrayList<>();//순열로 123 312 213 231..짝 뽑는순서
​​​​​​​​permutation(n, n, new int[n], temp, 0, 0);

​​​​​​​​for (int[] order : orders) {
​​​​​​​​​​​​int total = 0;
​​​​​​​​​​​​int[] point = new int[2];//최초커서위치 (r,c)
​​​​​​​​​​​​point[0] = r;
​​​​​​​​​​​​point[1] = c;
​​​​​​​​​​​​int[][] cBoard = new int[4][4];//grid 만들기
​​​​​​​​​​​​for (int i = 0; i < 4; i++) {
​​​​​​​​​​​​​​​​for (int j = 0; j < 4; j++) {
​​​​​​​​​​​​​​​​​​​​cBoard[i][j] = board[i][j];
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​​​​​for (int card : order) {//int[]인 order 즉, 순열로 나열한 순서 한가지씩. 123, 132, ...
​​​​​​​​​​​​​​​​int cnt = 0;
​​​​​​​​​​​​​​​​//목표 카드 찾기
​​​​​​​​​​​​​​​​cnt += bfs(cBoard, card, point) + 1;
​​​​​​​​​​​​​​​​//목표 카드 선택
​​​​​​​​​​​​​​​​cBoard[point[0]][point[1]] = 0;
​​​​​​​​​​​​​​​​System.out.println(point[0] + "," + point[1]);
​​​​​​​​​​​​​​​​//짝 찾기
​​​​​​​​​​​​​​​​cnt += bfs(cBoard, card, point) + 1;
​​​​​​​​​​​​​​​​//짝 찾기 성공
​​​​​​​​​​​​​​​​cBoard[point[0]][point[1]] = 0;
​​​​​​​​​​​​​​​​System.out.println(point[0] + "," + point[1]);

​​​​​​​​​​​​​​​​total += cnt;
​​​​​​​​​​​​}
​​​​​​​​​​​​System.out.println("total : " +total);
​​​​​​​​​​​​System.out.println("---");
​​​​​​​​​​​​answer = Math.min(total, answer);
​​​​​​​​}

​​​​​​​​return answer;
​​​​}

​​​​​​​​private int bfs(int[][] board, int target, int[] point) {
​​​​​​​​​​​​int r = point[0];
​​​​​​​​​​​​int c = point[1];
​​​​​​​​​​​​Queue<int[]> que = new LinkedList<>();
​​​​​​​​​​​​boolean[][] visited = new boolean[4][4];

​​​​​​​​​​​​que.offer(new int[]{r, c, 0});
​​​​​​​​​​​​visited[r][c] = true;

​​​​​​​​​​​​while (!que.isEmpty()) {
​​​​​​​​​​​​​​​​int[] p = que.poll();
​​​​​​​​​​​​​​​​if (board[p[0]][p[1]] == target) {
​​​​​​​​​​​​​​​​​​​​point[0] = p[0];
​​​​​​​​​​​​​​​​​​​​point[1] = p[1];
​​​​​​​​​​​​​​​​​​​​return p[2];
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​//4방 탐색
​​​​​​​​​​​​​​​​for (int d = 0; d < 4; d++) {
​​​​​​​​​​​​​​​​​​​​int nr = p[0] + dr[d];//direction 상하좌우 탐색
​​​​​​​​​​​​​​​​​​​​int nc = p[1] + dc[d];//direction 상하좌우 탐색
​​​​​​​​​​​​​​​​​​​​if (nr >= 0 && nr < 4 && nc >= 0 && nc < 4 && !visited[nr][nc]) {
​​​​​​​​​​​​​​​​​​​​visited[nr][nc] = true;
​​​​​​​​​​​​​​​​​​​​que.offer(new int[]{nr, nc, p[2] + 1});
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}

​​​​​​​​​​​​//ctrl + 4방 탐색
​​​​​​​​​​​​for (int d = 0; d < 4; d++) {
​​​​​​​​​​​​​​​​int[] result = findCard(board, p[0], p[1], d);
​​​​​​​​​​​​​​​​if ((result[0] != p[0] || result[1] != p[1]) && !visited[result[0]][result[1]]) {
​​​​​​​​​​​​​​​​​​​​visited[result[0]][result[1]] = true;
​​​​​​​​​​​​​​​​​​​​que.offer(new int[]{result[0], result[1], p[2] + 1});
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​return 0;
​​​​}

​​​​private int[] findCard(int[][] board, int r, int c, int d) {
​​​​​​​​r += dr[d];
​​​​​​​​c += dc[d];
​​​​​​​​while (r >= 0 && r < 4 && c >= 0 && c < 4) {
​​​​​​​​​​​​if (board[r][c] != 0) {
​​​​​​​​​​​​​​​​return new int[]{r, c};
​​​​​​​​​​​​}
​​​​​​​​​​​​r += dr[d];
​​​​​​​​​​​​c += dc[d];
​​​​​​​​}
​​​​​​​​return new int[]{r - dr[d], c - dc[d]};
​​​​}

​​​​private void permutation(int n, int r, int[] perms, int[] input, int depth, int flag) {
​​​​​​​​if (depth == r) {
​​​​​​​​​​​​int[] temp = new int[n];
​​​​​​​​​​​​System.arraycopy(perms, 0, temp, 0, n);
​​​​​​​​​​​​orders.add(temp);
​​​​​​​​​​​​return;
​​​​​​​​}
​​​​​​​​for (int i = 0; i < n; i++) {
​​​​​​​​​​​​if ((flag & (1 << i)) == 0) {
​​​​​​​​​​​​​​​​perms[depth] = input[i];
​​​​​​​​​​​​​​​​permutation(n, r, perms, input, depth + 1, flag | (1 << i));
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}
}