(Java) 프로그래머스 단체 사진 찍기

문제를 처음 읽고 설계까지 시간이 좀 걸렸다.

8명의 프렌즈로 순열을 만들면 되는 건데 최대 8! 이니 숫자가 크지 않아서 

dfs를 이용해 가능한 모든 순열을 만들고 조건을 검사하는것으로 생각했다.

만약 프렌즈의 숫자가 10을 넘어가는 숫자였다면

시간 초과가 날 가능성이 높아 백트래킹으로 풀었어야 할 것 같다.

 

최종 코드

class Solution {
    static int answer;
    static String[] arr = {"A", "C", "F", "J", "M", "N", "R", "T"};

     public int solution(int n, String[] data) {
        boolean[] visited = new boolean[8];
        answer = 0;
        dfs("", visited, data);
        return answer;
    }

    static void dfs(String orders, boolean[] visited, String[] data) {
        // 재귀 탈출문
        if (orders.length() == 8) {
            if (check(orders, data)) {
                answer++;
            }
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                String order = orders + arr[i];
                dfs(order, visited, data);
                visited[i] = false;
            }
        }
    }

    static boolean check(String orders, String[] data) {
        for (String s : data) {
            // 첫번째 프렌즈
            int first = orders.indexOf(s.charAt(0));
            // 두번째 프렌즈
            int second = orders.indexOf(s.charAt(2));
            // 조건
            char op = s.charAt(3);
            // 거리
            int length = Integer.parseInt(String.valueOf(s.charAt(4)));
            if (op == '=') {
                if (!(Math.abs(first - second) - 1 == length)) return false;
            } else if (op == '>') {
                if (!(Math.abs(first - second) - 1 > length)) return false;
            } else {
                if (!(Math.abs(first - second) - 1 < length)) return false;
            }
        }
        return true;
    }
}