관리 메뉴

막내의 막무가내 프로그래밍 & 일상

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

알고리즘/DFS, BFS, 시뮬, 백트래킹

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

막무가내막내 2021. 7. 6. 18:31
728x90

 

 

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

 

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

단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두

programmers.co.kr

 

 

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

 

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

Permalink This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository. Showing 1 changed file with 46 additions and 0 deletions. +46 −0 프로그래머스 단체사진 찍기 (2017 카카오코드 본

github.com

 

 

 

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

728x90
Comments