[프로그래머스,Level 2] 단체사진 찍기 (JAVA 구현)

 

- 첫 풀이 및 정답풀이

  이 문제는 주어진 요소들(카카오프렌즈)을 조건에 맞게 배치할 수 있는지 확인하는 문제이다. 즉, 모든 경우의 수를 완전 탐색으로 순회하며 조건에 맞는 경우를 카운트해주면 된다. 모든 경우의 수를 탐색하는 경우는 재귀 메서드를 이용하면 구할 수 있고 주어진 조건 문자열을 파싱 하여 알맞게 작성해주면 된다.

 

  단, 이 문제는 주의해야 할 점이 전역변수로 카운트했다면 solution 메서드 안에서 초기화를 해주어야 통과가 가능하다. 이유는 모르겠다.

import java.util.HashMap;


class Solution {
    // 1. 인덱스 방문 여부 체크 배열.
    static boolean check[] = new boolean[8];
    // 2. 카카오 프렌즈 0~7인덱스까지 각 알파벳을 매칭.
    static char friends[] = {'A','C','F','J','M','N','R','T'};
    
    static int answer;
    
    // 16. 주어진 조건 data에 맞는지 검사하는 메소드
    public static boolean isPossible(StringBuilder sb,String[] data){
        // 17. 조건 배열 data를 탐색.
        for(int i = 0 ; i<data.length;i++){
            // 18. 조건의 0번 인덱스와 2번 인덱스는 조건을 제시한 프렌즈, 상대 프렌즈이므로, 그 사이 거리를 구한다.
            // 단, 둘 사이의 프렌즈 수를 구해야 하기 때문에 최종 값에 -1.
            int gap = Math.abs(sb.indexOf(String.valueOf(data[i].charAt(0))) - sb.indexOf(String.valueOf(data[i].charAt(2))))-1;
            // 19. 조건의 4번 인덱스는 주어진 정수값.
            int condition_gap = data[i].charAt(4) - '0';
                        
            // 20. 조건의 3번 인덱스는 대소비교 문자이므로 이에 따라 분기처리.
            switch(data[i].charAt(3)){
                    // 21. 각 경우에 따라 조건에 맞지 않다면 false.
                case '=' :
                    if(gap != condition_gap) return false;
                    break;
                    
                case '>' :
                    if(gap <= condition_gap) return false;
                    break;
                    
                case '<':
                    if(gap >= condition_gap) return false;
                    break;                    
            }
            
        }
        
        // 22. 나머지는 true.
        return true;
    }
    
    // 6. dfs 메소드(인덱스, 경우의 수 순열을 저장할 객체, 조건 메소드에 전달 할 data 배열)
    public static void dfs(int idx,StringBuilder sb, String[] data){
        // 7. idx == 마지막 프렌즈인 경우 조건을 검사 및 종료.
        if(idx == friends.length){
            // 8. 조건 검사 메소드 호출.
            if(isPossible(sb,data)){
                answer++;
            } 
            return;
        }
        
        // 9. 전역변수로 선언한 문자형 배열을 탐색.
        for(int i = 0 ; i < friends.length;i++){
            // 10. 방문한 경우 패스.
            if(check[i]) continue;
            // 11. 방문처리 후,
            check[i] = true;
            // 12. 프렌즈에 해당하는 문자를 StringBuilder 객체에 붙인다. 
            sb.append(String.valueOf(friends[i]));
            // 13. 인덱스 증가 및 StringBuilder와 함께 재귀호출.
            dfs(idx+1,sb,data);
            // 14. 방문처리 해제.
            check[i] = false;
            // 15. 위에 붙인 문자를 다시 제거.
            sb.delete(idx,friends.length);           
        }    
    }
    
    public int solution(int n, String[] data) {
        // 3. 모든 경우의 수를 만들 StringBuilder 객체.
        StringBuilder sb = new StringBuilder();    
        // 4. 초기화 해주어야 통과가 된다.
        answer = 0;
        // 5. dfs메소드 호출.
        dfs(0,sb,data);      
        
        return answer;
    }
}