[JAVA] 프로그래머스 - 단체사진 찍기 ( 카카오 코드 2017 본선 )

 

 

문제를 처음에 잘못이해해서 왜 3648 가지가 나오는지 고민했는데 그냥 단순한 순열 문제였다.

 

# 3648 인 이유

 

N 과 F 는 이웃하면서 R과 T 사이에 3명이상 사람이 오는 경우의 수를 묻는다.

 

 

1) R 과 T사이에 NF포함 3명이 있는 경우

= 4! * 4C1 * 2! * 2! * 2! = 768

 

2) R 과 T 사이에 NF를 포함하지 않는 3명이 있는 경우

= 3! * 4C3 * 3! * 2! * 2! = 576

 

3) R 과 T 사이에 NF 포함 4명이 있는 경우

= 3! * 4C2 * 3! * 2! * 2! = 864

 

4) R과 T사이에 NF를 포함하지 않는 4명이 있는 경우

= 2! * 4! * 2! * 2! = 192

 

5) R 과 T 사이에 5명 있는 경우

= 2! * 4C3 * 4! * 2! * 2! = 768

 

6) R 과 T 사이에 6명 있는 경우

= 5! * 2! * 2! = 480

 

1) + 2) + 3) + 4) + 5) + 6) = 3648

 

 

이런식으로 DFS 의 순열속에서 맞는 모든 경우의 수를 찾아 주면 된다.

 

import java.util.*;

class Solution {
    static String[] d;
    static HashMap<Character,Integer> map ;
    static boolean[] visited;
    static int[] ch;
    static int answer;
    
    public int solution(int n, String[] data) {
        d = data;
        map = new HashMap<>();
        visited = new boolean[8];
        ch = new int[8];
        answer = 0;
        map.put('A',0);
        map.put('C',1);
        map.put('F',2);
        map.put('J',3);
        map.put('M',4);
        map.put('N',5);
        map.put('R',6);
        map.put('T',7);
        dfs(0);
        return answer;
    }
    
    public static void dfs(int idx){
        if(idx == 8){
            if(check()) answer++;
        }
        else{
            for(int i=0;i<8;i++){
                if(!visited[i]){
                    visited[i] = true;
                    ch[idx] = i;
                    dfs(idx + 1);
                    visited[i] = false;
                }
            }
        }
    }
    
    
    

    
    public static boolean check(){
        int a,b,res;
        char op;
        for(String s : d){
            a = ch[map.get(s.charAt(0))];
            b = ch[map.get(s.charAt(2))];
            op = s.charAt(3);
            res = s.charAt(4)-'0' + 1;
            
            if(op == '='){ if(Math.abs(a-b)!=res) return false;}
            else if(op == '>'){ if(Math.abs(a-b) <= res) return false;}
            else {if(Math.abs(a-b) >= res) return false;}
        }
        return true;
    }
}