[Algorithm/Java][프로그래머스] 단체사진 찍기

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

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

접근 방법

처음에 어떻게 접근하는지 모르겠어서 카카오 기술 블로그에 들어가서 해설을 봤는데
모든 경우를 다 세워보고 그 중에 조건을 만족하는지를 검사하는 방법이였다.
dfs를 이용해서 모든 경우의 줄을 세워보고 check 함수를 이용해서 조건을 만족하는지 검사해서 경우의 수를 셌다.

Code

import java.util.HashMap;
class Solution {
    public int answer = 0;
    public boolean[] visited = new boolean[8];
    String[] friends = {"A", "C", "F", "J", "M", "N", "R", "T"};
    public int solution(int n, String[] data) {
        dfs("",data);
        return answer;
    }
    // 모든 경우의 줄을 세우고
    // 줄의 길이가 8이 되었을 때, 주어진 조건을 만족하는지
    // check 함수를 사용해서 검사
    public void dfs(String line, String[] data){
        if(line.length() == 8){
            if(check(line, data)) answer++;
            return;
        }
        for(int i = 0; i<8; i++){
            if(!visited[i]){
                visited[i] = true;
                String newLine = line + friends[i];
                dfs(newLine, data);
                visited[i] = false;
            }
        }
    }
    // 조건을 만족하는지 검사하는 함수
    public boolean check(String line, String[] data) {
        for(String d: data){
            int idx1 = line.indexOf(d.charAt(0));
            int idx2 = line.indexOf(d.charAt(2));
            char op = d.charAt(3);
            int num = d.charAt(4) - '0' + 1;
            int diff = Math.abs(idx1-idx2);
            if(op == '='){
                if(diff != num) return false;
            }
            if(op == '<'){
                if(diff >= num) return false;
            }
            if(op == '>'){
                if(diff <= num) return false;
            }
        }
        return true;
    }
}