자바(JAVA) - 단체사진 찍기(Programmers : 1835)

 

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

코딩테스트 연습 - 단체사진 찍기

문제 이해하는데에 조금 어려움이 있었던 문제...

처음에는 String 정렬 쪽을 생각하며 한참을 고민하다가 존경하는 고수님의 풀이를 참고하여 문제를 풀 수 있었다.

정답은 DFS에 있었다. 각 프랜즈의 배치 + 검증 매소드를 통해 몇개 조합이 조건에 만족하는지 어렵지 않게 구할 수 있었다.

 

DFS 함수 안의 for문을 통해 각 프랜즈의 조합을 String으로 넘겨준다.

중복을 허용하지 않기 때문에 visited array를 사용하였으며, 모든 프랜즈가 포함된 상태일 때는 validator 메소드를 통해

모든 조건이 충족하는지 확인해주며 답을 구할 수 있었다.

class Solution {
    boolean[] visited;
    int answer = 0;
    String[] names = {"A", "C", "F", "J", "M", "N", "R", "T"};
    public int solution(int n, String[] data) {
        visited = new boolean[names.length];
        dfsSearch("", data);
        
        return answer;
    }
    
    public void dfsSearch(String currentNames, String[] datas) {
        if(currentNames.length() == names.length) {
            if(checkCondition(currentNames, datas)) answer++;  
            return;
        }
        
        for(int i = 0; i < names.length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                String tempName = currentNames + names[i];
                dfsSearch(tempName, datas);
                visited[i] = false;
            }
        }
    }
    
    public boolean checkCondition(String currentNames, String[] datas) {
        for(String data : datas) {
            int positionA = currentNames.indexOf(data.charAt(0));
            int positionB = currentNames.indexOf(data.charAt(2));
            char operator = data.charAt(3);                                        
            int distance = data.charAt(4) - '0';
            int actualDistance = Math.abs(positionA - positionB);    
            if(operator == '=') {
                if(actualDistance != distance + 1) return false;
            } else if (operator == '>') {
                if(!(actualDistance > distance + 1)) return false;
            } else if (operator == '<') {
                if(!(actualDistance < distance + 1)) return false;
            }
        }
        return true;
    }
}