[프로그래머스] 단체사진찍기 JAVA

AMUD·2022년 11월 25일
0

Algorithm

목록 보기
51/78

문제


문제링크

접근

  • 조건의 길이가 100이하로 작은 수이며, 사람이 8명이므로 완전탐색을 떠올렸다.
  • 모든 경우의 수를 방문하면서 조건에 부합하는지 확인하면 된다.
  • 유의할 점은 두 인덱스의 차가 거리가 아니라, (두 인덱스 차) - 1 이 거리가 된다는 것이다.

소스 코드

class Main {
    public static void main(String[] args) throws Exception {
        int n = 2;
        String[] data = { "N~F=0", "R~T>2" };
        Solution sol = new Solution();

        System.out.println("result : " + sol.solution(n, data));
    }
}

class Solution {
    int answer = 0;
    public int solution(int n, String[] data) {
        String[] people = { "A", "C", "F", "J", "M", "N", "R", "T" };
        boolean[] visited = new boolean[8];

        dfs(visited, people, data, "");

        return answer;
    }

    public void dfs(boolean[] visited, String[] people, String[] data, String shot) {
        if (shot.length() == 8) {
            if (check(shot, data))
                answer++;
            return;
        }

        for (int i = 0; i < 8; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(visited, people, data, shot + people[i]);
                visited[i] = false;
            }
        }
    }

    public boolean check(String str, String[] data) {
        for (String d : data) {
            int aIdx = str.indexOf(d.charAt(0));
            int bIdx = str.indexOf(d.charAt(2));
            int distance = Math.abs(aIdx - bIdx) - 1;

            char op = d.charAt(3);
            int operand = d.charAt(4) - '0';
            if (op == '=' && distance != operand) {
                return false;
            } else if (op == '<' && distance >= operand) {
                return false;
            } else if (op == '>' && distance <= operand) {
                return false;
            }
        }
        return true;
    }
}
profile
210's Velog :: Ambition Makes Us Diligent

0개의 댓글