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

문제

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

프로그래머스

 

---

문제 설명

카카오프렌즈는 소풍 중 단체사진을 찍기 위해 일렬로 서고자 합니다. 각 프렌즈는 특정한 배치 조건을 원하며, 이 조건들을 모두 만족하는 경우의 수를 계산해야 합니다.

조건의 형식은 다음과 같습니다:

• N~F=0: '네오'와 '프로도' 사이의 간격이 0이어야 합니다.
• R~T>2: '라이언'과 '튜브' 사이의 간격이 2칸 초과이어야 합니다.

각 조건은 다음과 같은 요소로 이루어져 있습니다:

• 첫 번째 글자와 세 번째 글자는 8명의 캐릭터 중 하나로, 각각 특정 캐릭터를 의미합니다.
• 네 번째 글자는 =, <, > 중 하나로, 두 캐릭터 사이의 간격 조건을 나타냅니다.
• 다섯 번째 글자는 간격을 나타내는 0 이상 6 이하의 숫자입니다.

목표는 모든 조건을 만족하는 가능한 서열의 경우의 수를 계산하는 것입니다.

접근 방법

1. 순열 생성: 8명의 캐릭터를 배열하여 일렬로 서는 모든 경우의 수를 생성합니다. 이는 총 8! (약 40,320)가지 경우의 수가 있습니다.
2. 조건 검증:
   • 각 순열에 대해 주어진 모든 조건을 확인합니다.
   • 각 조건의 두 캐릭터의 위치를 찾아 인덱스 차이를 계산하여 조건에 맞는지 검사합니다.
3. 카운트 증가:
   • 조건을 만족하는 순열일 경우, 유효한 경우의 수로 카운트합니다.

import java.util.*;

class Solution {
    private static int answer;
    private static final String[] characters = {"A", "C", "F", "J", "M", "N", "R", "T"};
    private static boolean[] visited = new boolean[8];

    public int solution(int n, String[] conditions) {
        answer = 0;
        findPermutations(0, new String[8], conditions);
        return answer;
    }

    private static void findPermutations(int depth, String[] arrangement, String[] conditions) {
        if (depth == arrangement.length) {
            Map<String, Integer> positionMap = new HashMap<>();
            for (int i = 0; i < arrangement.length; i++) {
                positionMap.put(arrangement[i], i);
            }
            if (isValid(positionMap, conditions)) {
                answer++;
            }
            return;
        }

        for (int i = 0; i < characters.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arrangement[depth] = characters[i];
                findPermutations(depth + 1, arrangement, conditions);
                visited[i] = false;
            }
        }
    }

    private static boolean isValid(Map<String, Integer> positionMap, String[] conditions) {
        for (String condition : conditions) {
            String first = condition.substring(0, 1);
            String second = condition.substring(2, 3);
            char op = condition.charAt(3);
            int distance = condition.charAt(4) - '0';

            int actualDistance = Math.abs(positionMap.get(first) - positionMap.get(second)) - 1;

            if (!checkCondition(actualDistance, distance, op)) {
                return false;
            }
        }
        return true;
    }

    private static boolean checkCondition(int actual, int required, char op) {
        switch (op) {
            case '=': return actual == required;
            case '<': return actual < required;
            case '>': return actual > required;
            default: return false;
        }
    }
}