[알고리즘] 프로그래머스 단체사진 찍기 (2017 카카오코드 본선) -DFS- 자바

 

 

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

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

 

 

프로그래머스 단체사진 찍기 문제를 풀어봤습니다. ㅎㅎ

 

8명의 카카오 프렌즈들이 사진을 찍는데 프렌즈의 규칙에 맞게 사진을 찍을 수 있는 경우의 수를 구하는 문제였습니다.

 

DFS로 완전탐색을 한 후 해당 순열이 조건을 만족하는 순열인지 구하는 방식으로 해결했습니다.

 

주석으로 추가 설명을  달아놨습니다.

 

풀이는 다음과 같습니다. 

 

[Java]

class Solution {
    private int answer = 0;
    private String[] friends = {"A", "C", "F", "J", "M", "N", "R", "T"};

    public int solution(int n, String[] data) {
        boolean[] isVisited = new boolean[8];
        dfs("", isVisited, data);
        System.out.println(answer);
        return answer;
    }

    private void dfs(String names, boolean[] isVisited, String[] datas) {
        if (names.length() == 7) {
            if (check(names, datas)) { // 조건만족 체크
                answer++;
            }
            return;
        }
        for (int i = 0; i < 8; i++) { // 조합
            if (!isVisited[i]) {
                isVisited[i] = true;
                String name = names + friends[i];
                dfs(name, isVisited, datas);
                isVisited[i] = false;
            }
        }
    }

    // 조건대로 섰는지 체크
    private boolean check(String names, String[] datas) {
        for (String data : datas) {
            int position1 = names.indexOf(data.charAt(0)); // 프렌즈 포지션1
            int position2 = names.indexOf(data.charAt(2)); // 프렌즈 포지션2
            char op = data.charAt(3); // 수식
            int index = data.charAt(4) -'0'; // 간격
            if (op == '=') {
                if (!(Math.abs(position1 - position2) == index+1)) return false; //둘 포지션 차이를 구하기 위해선 index+1 을 해야함에 주의
            } else if (op == '>') {
                if (!(Math.abs(position1 - position2) > index+1)) return false;
            } else if (op == '<') {
                if (!(Math.abs(position1 - position2) < index+1)) return false;
            }
        }
        return true;
    }
}

https://github.com/mtjin/algorithm_practice/commit/34b8d6243d0ad9f3ed01fa28c4613b6561855e8a

프로그래머스 단체사진 찍기 풀이 · mtjin/algorithm_practice@34b8d62

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!!