(프로그래머스) 리틀 프렌즈 사천성

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

 

참고로 이 문제는 프로그래머스에서 문제를 풀 때 전역변수로 등록된 값들을 main함수에서 초기화를 해줘야 통과가 된다.

 

🐢 설명

한쌍의 짝으로 존재하는 카드들에 대해서 단 두번의 이동으로 매칭이 될 수 있는지 없는지 확인하고 결과적으로 모든 카드가 매칭이 될 수 있는지 확인하는 문제이다.

• 하나의 카드의 쌍이 매칭이 되면 해당 카드는 제거 되며 공백이 된다.
• 모든 카드의 쌍이 제거되면 제거된 카드를 순서대로 문자열로 반환한다.
• 모든 카드 쌍을 제거할 수 없다면 IMPOSSIBLE을 반환하면 된다.

 

해결을 위한 로직

1. 지도에 카드 쌍은 무조건 1 대 1로 존재한다고 되어있으므로 모든 카드의 종류를 list에 담고, 각 카드 별 두개의 위치를 map을 이용하여 담는다.
2. 모든 카드 종류를 담은 list를 정렬하고 하나 뽑아서 매칭이 가능한지 확인한다.
3. 매칭에 성공한 경우 해당 카드를 지우고, 문자열에 카드의 문자를 적고, 다시 처음 카드 부터 확인한다. 그렇게 모든 카드가 제거 될 때까지 진행한다.
4. 모든 카드가 제거되면 문자열을 반환한다.

이때, 가장 중요한 부분은 매칭이 가능한지 확인하는 부분으로, 두가지 경로에 대해 탐색을 해줘야 한다.

 

우리는 리스트에 카드를 담을 때 2차원 배열을 돌면서 담았으므로 첫번째 카드의 y축이 두번째 카드의 y축보다 위에 있다는 사실을 알고 있으므로, x축의 값만 확인해서 찾아주면 된다. 또한 열을 맞추고 행을 맞출지 or 행을 맞추고 열을 맞출지 정하면 된다.

 

아래에서는 rowMatch(), colMatch() 두개를 사용했는데 첫인자는 고정 인덱스, 두번째와 세번째는 탐색을 위한 범위 값으로 사용된다. 이때 어떤 함수를 먼저 수행했냐에 따라 인자로 전달되는 값이 변경된다. 

만약, rowMatch()를 먼저 수행했다면 고정 인덱스는 시작 x값이며 탐색범위는 시작 y부터 도착 y가 될 것이다. 이후 탐색이 성공적으로 끝나면 y축은 도착 지점과 동일해졌다는 것이 자명하므로 다음 탐색은 colMatch()를 하면 된다. 이때는 고정 인덱스로 도착 y를 주고, 탐색 범위는 시작 x부터 도착 x가 된다. (시작 x < 도착 x 일 경우에) 이는 탐색 순서를 변경하면 인자도 적절하게 바꿔주면 된다.

 

🐢코드

import java.util.*;

class Solution {
    static char[][] table;
    static int N, M;
    static StringBuilder answer = new StringBuilder();
    static HashMap<Character, int[][]> map = new HashMap<>();
    static ArrayList<Character> list = new ArrayList<>();

    public String solution(int m, int n, String[] board) {
        N = m;
        M = n;

        answer = new StringBuilder();
        map.clear();
        list.clear();
        table = new char[N][M];
        
        for (int i = 0; i < N; i++) {
            String line = board[i];
            for (int j = 0; j < M; j++) {
                table[i][j] = line.charAt(j);
                if (table[i][j] != '.' && table[i][j] != '*') {
                    if (!map.containsKey(table[i][j])) {
                        list.add(table[i][j]);
                        map.put(table[i][j], new int[2][2]);
                        map.get(table[i][j])[0][0] = i;
                        map.get(table[i][j])[0][1] = j;
                    } else {
                        map.get(table[i][j])[1][0] = i;
                        map.get(table[i][j])[1][1] = j;
                    }
                }
            }
        }

        list = new ArrayList<>(map.keySet());
        list.sort(null);

        int idx = 0;
        while (list.size() != 0) {
            if (canMatch(map.get(list.get(idx)), list.get(idx))) {
                char c = list.remove(idx);
                answer.append(c);
                deleteBlock(c);
                idx = 0;
            } else {
                idx++;
                if (idx == list.size())
                    return "IMPOSSIBLE";
            }
        }
        return answer.toString();
    }

    private static void deleteBlock(char c) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (table[i][j] == c) {
                    table[i][j] = '.';
                }
            }
        }
    }

    private static boolean canMatch(int[][] dots, char target) {
        int sy = dots[0][0];
        int sx = dots[0][1];
        int dy = dots[1][0];
        int dx = dots[1][1];

        // 출발 x가 도착 x보다 작은 경우
        if (sx < dx) {
            // row를 맞추면 다음 colMatch때는 y축을 도착 y로 잡고, sx 부터 dx까지 확인한다.
            if (rowMatch(sx, sy, dy, target) && colMatch(dy, sx, dx, target)) {
                return true;
            }
            if (colMatch(sy, sx, dx, target) && rowMatch(dx, sy, dy, target)) {
                return true;
            }
        } else {
        // 출발 x가 도착 x보다 크거나 같은 경우
            if (rowMatch(sx, sy, dy, target) && colMatch(dy, dx, sx, target)) {
                return true;
            }
            if (colMatch(sy, dx, sx, target) && rowMatch(dx, sy, dy, target)) {
                return true;
            }
        }
        return false;
    }

    private static boolean colMatch(int fixY, int fromX, int toX, char target) {
        for (int i = fromX; i <= toX; i++) {
            if (table[fixY][i] != '.' && table[fixY][i] != target)
                return false;
        }
        return true;
    }

    private static boolean rowMatch(int fixX, int fromY, int toY, char target) {
        for (int i = fromY; i <= toY; i++) {
            if (table[i][fixX] != '.' && table[i][fixX] != target)
                return false;
        }
        return true;
    }
}

 

🐢 마무리