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

각 data[i]는 다섯 글자로 구성된 문자열
A,C,F,J,M,N,R,T -> 8 사람
data[i]는 조건 : N~F=0 -> 즉 다섯 글자
data[i].charAt(0) ,data[i].charAt(2)는 사람
data[i].charAt(1)은 항상 "~"
data[i].charAt(3)는 =,<.> 중 하나,
data[i].charAt(4) : 두 프렌즈 사이에 있는 다른 프렌즈의 수

풀이생각 : 완전탐색

(60분... 매우 쉬워서 20분이면 다 풀겠다 햇는데..... 계속 이상한 실수를 하고 있었다 . 실수도 실력이지)

구해야 하는 것 : 모든 조건을 만족하는 "경우의 수"
조건의 개수 n은 100이하이다.

====첫 번째 생각: 완전탐색======
모든 조합에 대해 완전탐색하며, 각 경우마다 모든 조건을 만족하는지 확인 한다

• 조합의 개수 ? 8! = 4만

• 매 조합마다 확인 할 것? 최대 100개

• 400만 정도니까 해 볼만 한 듯하다.

  이를 위해, 특정 조합 때, 각 캐릭터의 위치를 저장하는 loc을 두었다.
  data[i]로부터 특정 캐릭터에 해당하는 알파벳을 매핑하는 Map을 만들어 두었다. (수가 적어서 array에서 순차적으로 탐색해도 되지만 )

import java.util.*;
class Solution {

    public Map<Character,Integer> map = new HashMap<>();
    //"A","C","F","J","M","N","R","T"}
    //  0  1   2   3  4   5    6   7
    public String[] p = new String[]{"A","C","F","J","M","N","R","T"};
    public int[] loc = new int[8];  // 각 사람의 위치를 저장한다.
    public boolean[] visit = new boolean[8];
    public int cnt =0;
    public String[] gdata;
    //public static PrintStream fileOu;
    public int solution(int n, String[] data){
        int answer = 0;
        gdata = data;
        setting();
        combi(0);
        answer =cnt;
        return answer;
    }
    public void setting(){
        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);
    }
    public void combi(int m){
        if(m>=8){
            if(check()==false)return;
            cnt++;
            return;
        }
        for(int i=0;i<p.length;i++){
            if(visit[i])continue;
            visit[i] = true;
            loc[i] = m;
            combi(m+1);
            visit[i]=false;
        }
        return;

    }
    // 조건을 만족하는가?
    public boolean check(){
        int c=0; // c는 조건인 간격 (사람의 수)
        int dist=0; // 실제 간격 ( 사람의 수 )
        char log;
        for(String cond:gdata){
            dist = Math.abs(loc[map.get(cond.charAt(0))]-loc[map.get(cond.charAt(2))]);
            dist--; // 사이에 있는 사람의 수여야 하니까
            c = cond.charAt(4)-'0';
            log = cond.charAt(3);
            switch(log){
                case '=':
                    if(dist!=c){
                        return false;
                    }
                    break;
                case '<':
                    if(dist>=c){
                        return false;
                    }
                    break;
                case '>':
                    if(dist<=c){
                        return false;
                    }
                    break;
            }
        }
        return true;
    }
}