[ 프로그래머스 ] #1835 : 단체사진 찍기 - JAVA

🔗단체사진 찍기

import java.util.ArrayList;
import java.util.List;

class Solution {

    static char[]friends={'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    static int count =0;

    public int solution(int n, String[] data) {
        //{조건을 제시한 프렌즈}~{상대방}{=,<,>}{두 프렌즈 사이 사른 프렌즈의 수}
        //모든 조건을 만족할 수 있도록 서는 경우의 수를 계산

        count =0;
        boolean[]visited=new boolean[friends.length];
        List<Character> arrange=new ArrayList<>();
        generate(arrange,visited,data);
        return count;
    }

    //순열 생성 
    private static void generate(List<Character> arrange,boolean[] visited, String[] data){

        // 모든 friend들에 대해 순열이 완성되었다면
        if(arrange.size()==friends.length){

            //해당 순열이 주어진 조건에 타당한지 검사
            if(isValid(arrange,data)){// 타당하면
                count++;// 경우의 수 증가
            }
            return;
        }

        // friends 순서대로 배치
        for(int i=0;i<friends.length;i++){
            if(!visited[i]){// 방문하지 않았다면
                visited[i]=true;//방문한다.
                arrange.add(friends[i]);//arrange에 추가
                generate(arrange,visited,data);// 그 arrange를 기반으로 순열 생성(재귀)

                //가장 최근에 추가 한거 삭제 -> 백트래킹
                arrange.remove(arrange.size()-1);
                visited[i]=false;
            }
        }
    }

    private static boolean isValid(List<Character> arrange, String[]data){
        for(String condition : data){

            char friend1=condition.charAt(0);
            char friend2=condition.charAt(2);
            char operator=condition.charAt(3);
            int distance=condition.charAt(4)-'0';

            // 현재 순열에서 friend들의 위치
            int pos1=arrange.indexOf(friend1);
            int pos2=arrange.indexOf(friend2);

            // 거리 계산
            int actualDistance=Math.abs(pos1-pos2)-1;

            // 거리가 조건에 맞는 지 검사
            if(operator=='='&& actualDistance != distance){
                return false;
            }else if(operator=='<'&& actualDistance >= distance){
                return false;
            }else if(operator=='>'&& actualDistance <= distance){
                return false;
            }

        }
        return true;
    }
}