단체 사진찍기 - 프로그래머스 (Java, Level 2)

 

전체적인 흐름

프렌즈들이 설 수 있는 전체 경우의 수는 8!이다.

이 모든 경우에 대해서 모든 조건이 맞는지 각각 따져본다.

 

즉, DFS로 프렌즈를 쭉 배치한 뒤, 8명이 다 섰을 때 해당 배치가 조건과 맞는지 체크한다.

 

프렌즈를 모든 경우의 수로 배치하는 메소드 (arrange())

배치를 파라미터로 받고, 해당 배치가 조건들과 맞는지 확인하는 메소드 (check())

 

    final char[] FRIENDS = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    boolean[] isUsed = new boolean[FRIENDS.length];
    int answer = 0;
    //매번 data를 파라미터로 넘기지 말고 전역변수로
    String[] conditions;
    
    public int solution(int n, String[] data) {

        StringBuilder sb = new StringBuilder();
        
        //전역변수 conditions가 data 참조
        conditions = data;

        arrange(0, sb);
        
        return answer;
    }//solution() 
    
    public void arrange(int idx, StringBuilder sb) {
        if(idx==FRIENDS.length) {
            //8명 배치 다 됐으면, 조건 검사 통과하면 answer 값 증가
            if(check(sb)) answer++;
            return;
        }//if end

        for(int i=0; i<FRIENDS.length; i++) {
            if(!isUsed[i]) {
                sb.append(FRIENDS[i]);
                isUsed[i] = true;
                arrange(idx+1, sb);
                isUsed[i] = false;
                //위에 붙인 문자열 제거
                sb.delete(idx, sb.length());
            }//if end
        }//for end
    }//combination() end

    //조건에 맞는지 확인하는 메소드
    public boolean check(StringBuilder sb) {
        String friend1;
        String friend2;
        char operator;
        int gap;
        int realGap;

        for (String condition : conditions) {
            friend1 = String.valueOf(condition.charAt(0));
            friend2 = String.valueOf(condition.charAt(2));
            operator = condition.charAt(3);
            //char->int
            gap = condition.charAt(4) - '0';

            realGap = Math.abs(sb.indexOf(friend1)-sb.indexOf(friend2))-1;

            switch(operator) {
                case '=' :
                    if(realGap != gap) return false;
                    break;
                case '<' :
                    if(realGap >= gap) return false;
                    break;
                case '>' :
                    if(realGap <= gap) return false;
                    break;
            }//switch end
        }//for end

        return true;
    }//check() end