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

문제설명

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

구현방법

• DFS를 이용하여 8명의 캐릭터를 줄세우는 모든 경우를 구함
• 각 경우마다 주어진 조건을 만족하는지 체크, 만족하면 count+1

주의사항

• count를 전역변수로 선언하고 값을 0으로 초기화 하니 채점에서 실패.
• count 변수 초기화를 solution함수 내에서 진행하니 정상적으로 동작함.

코드

import java.util.*;
class Solution {
    static char[] friends = {'A','C','F','J','M','N','R','T'};
    static Stack<Character> st = new Stack<>();
    static boolean visit[];
    static String restrict[];
    static int count;
    public int solution(int n, String[] data) {
        count=0;
        visit = new boolean[8];
        restrict = data;
        Arrays.fill(visit,false);
        for(int i=0;i<8;i++){
            dfs(i,1);
        }
        return count;
    }
    public void dfs(int start, int depth){
        st.push(friends[start]);
        if(depth==8){
            if(check()){
               count++; 
            }
            st.pop();
            return;
        }
        visit[start] = true;
        for(int i=0;i<8;i++){
            if(!visit[i]){
                dfs(i,depth+1);
                visit[i] = false;
            }
        }
        visit[start] = false;
        st.pop();
    }
    public boolean check(){
        for(String t : restrict){
                if(t.charAt(3)=='='){
                    if(Integer.parseInt(t.charAt(4)+"")+1!=Math.abs(st.indexOf(t.charAt(0))-st.indexOf(t.charAt(2)))){
                        return false;
                    }
                }
                else if(t.charAt(3)=='<'){
                   if(Integer.parseInt(t.charAt(4)+"")+1<=Math.abs(st.indexOf(t.charAt(0))-st.indexOf(t.charAt(2)))){
                       return false;
                   }
                }
                else{
                    if(Integer.parseInt(t.charAt(4)+"")+1>=Math.abs(st.indexOf(t.charAt(0))-st.indexOf(t.charAt(2)))){
                       return false;
                   }
                }
            }
        return true;
    }
}