[프로그래머스 Level 2] 단체사진 찍기 (Java)

🚀링크

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

💻문제

🌏문제 풀이

우선, 완전탐색을 이용하여 8명의 프렌즈들이 사진을 찍기 위해 일렬로 설 수 있는 모든 경우의 수를 찾습니다.

하나의 경우가 만들어질때마다 data 배열에 주어진 조건을 확인하고, 모든 경우를 만족할 경우에만 answer의 값을 1씩 올려줍니다.

마지막으로, answer의 값을 리턴해주면 문제를 해결할 수 있습니다.

💻코드

class Solution {
    
    static int answer;
    static int[] selected;
    static char[] chars = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    
    public int solution(int n, String[] data) {
        answer = 0;
        
        selected = new int[8];
        
        recur(data, 0);
        
        return answer;
    }
    
    static void recur(String[] data, int k) {
        if(k == 8) {
            for(int i = 0; i < data.length; i++) {
                char friend = data[i].charAt(0);
                char opponent = data[i].charAt(2);
                char condition = data[i].charAt(3);
                int dist = Character.getNumericValue(data[i].charAt(4));
                
                int friend_idx = findIndex(friend); // 프렌지의 위치
                int opponent_idx = findIndex(opponent); // 상대방의 위치
                
                // 주어진 조건을 만족하는지 확인
                // 조건을 만족하지 않으면, return을 해서 탐색을 종료
                if(condition == '>') {
                    if(Math.abs(friend_idx - opponent_idx) - 1 <= dist) {
                        return;
                    }
                } else if(condition == '<') {
                    if(Math.abs(friend_idx - opponent_idx) - 1 >= dist) {
                        return;
                    }
                } else if(condition == '=') {
                    if(Math.abs(friend_idx - opponent_idx) - 1 != dist) {
                        return;
                    }
                }
            }
            answer++;
            return;
        }
        for(int i = 0; i < 8; i++) {
            // 중복 여부를 확인
            boolean isSelected = false;
            for(int j = 0; j < k; j++) {
                if(selected[j] == i) {
                    isSelected = true;
                }
            }
            
            // 중복되지 않는 값일 경우
            if(!isSelected) {
                selected[k] = i;
                recur(data, k + 1);
                selected[k] = -1;
            }
        }
    }
    
    // 프렌즈의 위치를 찾아서 리턴
    static int findIndex(char c) {
        for(int i = 0; i < selected.length; i++) {
            if(chars[selected[i]] == c) {
                return i;
            }
        }
        
        return -1;
    }
}