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

1. 문제

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

프로그래머스

 

2. 설명

경우의 수 최대가 8!이기 때문에 재귀를 사용했다.

backtracking을 사용해서 경우의 수를 줄이려고 했는데,

검사하는 경우의 수는 줄었지만 결과적으로 시간은 늘어났다.

왜지

 

3. 코드

class Solution {
    static char[] friends = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    static boolean[] visited;
    static char[] position;
    static int answer;
    
    public int solution(int n, String[] data) {
        answer = 0;
        visited = new boolean[8];
        position = new char[8];
        
        backtracking(0, n, data);
        return answer;
    }
    
    void backtracking(int idx, int n, String[] data) {
        if(idx == 8) {
            answer++;
        }
        else {
            for(int i=0; i<8; i++) {
                if(!visited[i]) {
                    visited[i] = true;
                    position[idx] = friends[i];
                    // 조건을 만족할 경우에만 실행
                    if(isPossible(idx +1, n, data))
                        backtracking(idx + 1, n, data);
                    visited[i] = false;
                }
            }
        }
    }
    
    boolean isPossible(int idx, int n, String[] data) {
        for(int i=0; i<n; i++) {
            char[] condition = data[i].toCharArray();
            int from = -1, to = -1;
            for(int j=0; j<idx; j++) {
                if(position[j] == condition[0]) from = j;
                if(position[j] == condition[2]) to = j;
            }
            if(from < 0 || to < 0)
                return true;
            // 프렌즈와의 간격
            int gap = Math.abs(from - to) -1;
            int len = condition[4] - '0';
            switch(condition[3]) {
                case '=' : 
                    if(gap != len) return false;
                    break;
                case '>' : 
                    if(gap <= len) return false;
                    break;
                case '<' : 
                    if(gap >= len) return false;
                    break;
            }
        }
        return true;
    }
}