프로그래머스 코딩테스트 연습 Level2 - 단체 사진 찍기 [ Java ]

나올 수 있는 경우의 수가 8! = 40320이고 조건이 최대 100개밖에 되지 않으므로 모든 경우의 수에 대한 모든 조건을 확인한다고 해도 4032000번만 확인하면 되므로 모든 경우의수를 확인합니다.

 

class Solution {
        static boolean[] visited = new boolean[127]; // 캐릭터 사용 여부 ex visitd['A'] = true : 어피치 방문함
    static int[] position = new int[127]; // 캐릭터의 위치 ex position['A'] = 0 'A'는 0번에 있다.
    static int count = 0;
    static boolean check(String[] data) {
        for (String str : data) {
            char a = str.charAt(0); // 첫 번째 캐릭터
            char b = str.charAt(2); // 두 번째 캐릭터
            int len = Math.abs(position[a] - position[b]); // 현재 길이
            char sign = str.charAt(3); // 등호나 부등호
            int expectLen = str.charAt(4) - '0' + 1; // 조건의 길이
            if (sign == '>' && len <= expectLen)
                return false;
            else if (sign == '<' && len >= expectLen)
                return false;
            else if (sign == '=' && len != expectLen)
                return false;
        }
        return true;
    }

    static void bt(int depth, String[] data) {
        if (depth == 8) {
            if (check(data)) count++;
            return;
        }

        for (char c : new char[] {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'}) {
            if (visited[c]) continue;
            visited[c] = true;
            position[c] = depth;
            bt(depth + 1, data);
            visited[c] = false;
        }
    }

    public int solution(int n, String[] data) {
        count = 0;
        bt(0, data);
        return count;
    }
}