[프로그래머스] 단체사진 찍기 (Java)

문제

https://programmers.co.kr/learn/courses/30/lessons/1835?language=java 

코딩테스트 연습 - 단체사진 찍기

프로그래머스 단체사진 찍기

풀이

완전 탐색과 DFS로 풀었다. 

데이터 개수가 8개로 정해져 있고 크지 않기 때문에 시간초과는 발생하지 않았다. 

모든 경우의 수를 구하고,  rule에 부합하지 않는 케이스는 count 하지 않는다. 

소스코드

import java.util.*;
class Solution {
    public boolean[] used;
    public char[] arr;
    public String[] data;
    public int answer;
    public int solution(int n, String[] data) {
        this.answer = 0;
        this.data = data;
        arr = new char[]{'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'}; 
        used = new boolean[arr.length];        
        dfs("", 0);
        return answer;
    }
    
    public void dfs(String str, int len){
        if(len == arr.length) {
            if(isPossible(str)) answer++;
            return;
        }
        for(int i = 0; i < arr.length; i++){
            if(used[i]) continue;
            used[i] = true;
            dfs(str+arr[i], len+1);
            used[i] = false;
        }
    }
    
    public boolean isPossible(String str){
        for(String rule : data){
            int idx1 = str.indexOf(String.valueOf(rule.charAt(0)));
            int idx2 = str.indexOf(String.valueOf(rule.charAt(2)));
            char oper = rule.charAt(3);
            int diff = Integer.parseInt(String.valueOf(rule.charAt(4)));
            int realDiff = Math.abs(idx1-idx2)-1;
            if ((oper == '<') && !(realDiff < diff)) return false;
            else if ((oper == '>') && !(realDiff > diff)) return false;
            else if ((oper == '=') && !(realDiff == diff)) return false;
        }
        return true;
    }
}