[Lv.2] 단체사진 찍기

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

class Solution {
    int cnt;

    boolean[] isUsed;
    List<Condition> conditionList;
    public int solution(int n, String[] data) {
        conditionList=new ArrayList<>();
        isUsed=new boolean[8]; //{A, C, F, J, M, N, R, T} = 0,1,2,3,4,5,6,7
        cnt=0;
        for (String req : data) {
            char a=req.charAt(0);
            char b=req.charAt(2);
            char state=req.charAt(3);
            char num=req.charAt(4);
            conditionList.add(new Condition(toInt(a),toInt(b),state,num-'0'));
        }
        dfs(0,"");
        return cnt;
    }
    public void dfs(int depth,String data){
        //System.out.println("now depth:"+depth+ " data : "+data);
        if(depth==8){
            //made
            cnt++;
            return;
        }

        for(int i=0;i<8;i++){
            if(!isUsed[i]){
                //System.out.println("Found Not used:"+i+"/ in depth:"+depth);
                if(isPossible(i,data)){
                    String origin=data;
                    data=data+ i;
                    isUsed[i]=true;
                    dfs(depth+1,data);
                    isUsed[i]=false;
                    data=origin;
                }
            }
        }

    }
    private boolean isPossible(int i,String data){
        //System.out.println("will find is is possible");
        if(data.length()==0)
            return true;
        for (Condition condition : conditionList) {
            if(condition.u1==i||condition.u2==i){
                //현재 추가할 대상과 관련된 조건이 있다면
                //System.out.println("there is a condition");
                int opposite;
                if(condition.u1==i)
                    opposite=condition.u2;
                else opposite=condition.u1;
                for (int j = 0; j < data.length(); j++) {
                    if(data.charAt(j)==opposite+'0'){
                        //현재 줄에 타겟과 연관된 조건이 있다.
                        int dis=data.length()-j-1;
                        //System.out.println("ok compare, dis:"+dis+" / num:"+condition.num);
                        if(condition.cond=='='){
                            if(condition.num!=dis){
                                //System.out.println("false1");
                                return false;
                            }
                        }else if(condition.cond=='<'){
                            if(condition.num<=dis){
                                //System.out.println("false2");
                                return false;
                            }
                        }else{
                            if(condition.num>=dis){
                                //System.out.println("false3");
                                return false;
                            }
                        }

                    }
                }

            }
        }


        return true;
    }
    class Condition{
        int u1,u2;
        char cond;
        int num;

        public Condition(int u1, int u2, char cond, int num) {
            this.u1 = u1;
            this.u2 = u2;
            this.cond = cond;
            this.num = num;
        }
    }
    public int toInt(char c){
        if(c=='A')
            return 0;
        else if(c=='C')
            return 1;
        else if(c=='F')
            return 2;
        else if(c=='J')
            return 3;
        else if(c=='M')
            return 4;
        else if(c=='N')
            return 5;
        else if(c=='R')
            return 6;
        else
            return 7;


    }
}

---

처음엔 경우의 수 세워서 수학적으로 푸는건가 싶었지만, 그렇게는 못풀거같아서 dfs로 풀었다.

시간초과날 것 같다는 생각과 함께 테스트 케이스를 돌려보니 맞았다 !

그래서, 제출해보니 바로 실패가 떴다.

한참 왜 시간초과도 아니고 틀린거지 생각해보다 답이 나오지 않아 질문게시판을 들어가보니 이 문제의 경우 한 케이스 내에서 여러번 검증을 하는 것 같아서, 전역변수를 solution메소드 안에서 초기화 하라고 했다.

놀랍게도, 로직에 손도 안대고 그냥 전역변수 초기화를 solution안에서 해주니 바로 통과되었다 .. !