프로그래머스-단체사진 문제

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

문제 풀이

1. 이 문제를 푸려면 순열을 이해해야한다.
2. 제한 조건

• 1 <= n <= 100
  data의 원소는 다섯 글자로 구성된 문자열이다. 각 원소의 조건은 다음과 같다.
• 첫 번째 글자와 세 번째 글자는 다음 8개 중 하나이다. {A, C, F, J, M, N, R, T} 각각 어피치, 콘, 프로도, 제이지, 무지, 네오, 라이언, 튜브를 의미한다. 첫 번째 글자는 조건을 제시한 프렌즈, 세 번째 글자는 상대방이다. 첫 번째 글자와 세 번째 글자는 항상 다르다.
• 두 번째 글자는 항상 ~이다.
• 네 번째 글자는 다음 3개 중 하나이다. {=, <, >} 각각 같음, 미만, 초과를 의미한다.
• 다섯 번째 글자는 0 이상 6 이하의 정수의 문자형이며, 조건에 제시되는 간격을 의미한다. 이때 간격은 두 프렌즈 사이에 있는 다른 프렌즈의 수이다.

이해하기

data의 원소는 다섯 글자로 구성된 문자열이고, 이 원소로 이루어진 배열의 집합이다. 즉, 여러개의 조건이 올 수 있다는 뜻이다.

두번째 글자는 항상 ~이다.
네 번째 글자는 조건식이므로 간격의 조건을 말하는 것이고 다섯번째 글자는 칸수를 의미한다. 즉
N~F>=2는 N과 F의 간격은 2이상이어야 한다는 뜻이다. 이러한 조건을 문자열로 주었을 때, 이 문자열을 분석하여 경우의 수를 출력할 수 있어야 한다.

문제풀이

class Solution {
    static int answer = 0;
    static char[] people = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    
    public int solution(int n, String[] data) {
        answer = 0; //출력할 경우의 수 
        char[] ch = new char[8];//단체 사진을 찍을 사람들의 모음.
        boolean[] visit = new boolean[8];//사람 할당 체크.
        dfs(0, ch, visit, n, data);
        return answer;
    }
     
    void dfs(int k, char[] ch, boolean[] visit, int n, String[] data){
    	//주어진 조건을 전부 방문하여 경우의 수를 카운트한다.
        if(k==8){
        	for(int i=0; i<n; i++) {
        		int interval = 0;
        		int cnt = 0;
                for(int j=0; j<8; j++){
                    if(ch[j] == data[i].charAt(0) || ch[j] == data[i].charAt(2)){
                        cnt++;
                        continue;
                    }
                    if(cnt==1){
                        interval++;
                    }else if(cnt==2){
                        break;
                    }
                }
        		if(data[i].charAt(3)=='='){
                    if(interval != data[i].charAt(4) - '0') return;
                }else if(data[i].charAt(3)=='<'){
                    if(interval >= data[i].charAt(4) - '0') return;
                }else if(data[i].charAt(3)=='>')
                    if(interval <= data[i].charAt(4) - '0') return;
        	}
        	answer++;
        	return;
        }
        //모든 경우의 수에 접근할 수 있도록 8명의 사람을 모두 집어넣어 카운트를 실행한다.
        for(int i=0; i<8; i++){
            if(!visit[i]){
                ch[k] = people[i];
                visit[i] = true;
                dfs(k+1,ch,visit,n,data);
                visit[i] = false;
            }
        }
    }
}