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

• 문제

풀이과정

• 문제를 풀기에 앞서, 문제에 주어진 조건을 먼저 살펴보면 단체사진을 찍을 프렌즈는 8명으로 고정되어있음을 알 수 있다. 즉, 만일 무조건 만족할 수 있는 조건만 주어졌다면 최대 8! = 40320 개의 경우의 수가 존재함을 알 수 있다.
• 조건의 최대 갯수는 100개로 주어졌다. 따라서 모든 가능한 경우의 수를 먼저 계산한 후, 각각의 경우의 수가 조건을 만족하는지를 확인하게 된다면 최대 약 400만 번의 조건 확인 작업을 거치게 될 것임을 알 수 있다.
• 위의 두 가지 점으로부터 미루어 보아 조건을 생각하지 않고 모든 가능한 경우의 수를 먼저 구한 후, 각각의 경우의 수가 주어진 조건을 모두 만족하는지 검사하여도 크게 시간적으로 무리가 가지 않을것이라 예상하였다.
• 풀이과정은 아래와 같은 과정을 따랐다.
  1. 카카오 프렌즈 8명을 배치할 수 있는 모든 경우의 수를 구한다. (40,320 가지)
     • Java 에서는 Permutation 코드가 내장 패키지로 제공되지 않기에 이곳을 참고로 하였다.
  2. 각각의 경우의 수가 주어진 조건을 모두 만족하는지 확인하여, 만족하는 수를 카운팅한다.

Code

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public static Queue<String> candidates;

    public int solution(int n, String[] data) {
        int count = 0;
        candidates = new ArrayDeque<>(40320);

        // 1. 먼저, 프렌즈들을 배치할 수 있는 모든 경우의 수를 계산한다.
        char[] chars = "ACFJMNRT".toCharArray();
        permutation(chars, 0, 8);

        // 2. 각각의 배치 가능한 경우에 대해서, 주어진 제한 조건을 모두 만족하는지 확인한다.
        while (!candidates.isEmpty()) {
            String candidate = candidates.poll();
            if (passConditions(candidate, data)) {
                count++;
            }
        }

        return count;
    }

    private boolean passConditions(String candidate, String[] conditions) {
        for (String condition : conditions) {
            char proposer = condition.charAt(0);
            char target = condition.charAt(2);
            char operator = condition.charAt(3);
            int targetDistance = condition.charAt(4) - '0';

            int proposerPosition = candidate.indexOf(proposer);
            int targetPosition = candidate.indexOf(target);

            switch (operator) {
                case '=':
                    if (Math.abs(targetPosition - proposerPosition) - 1 != targetDistance) {
                        return false;
                    }
                    break;
                case '<':
                    if (Math.abs(targetPosition - proposerPosition) - 1 >= targetDistance) {
                        return false;
                    }
                    break;
                case '>':
                    if (Math.abs(targetPosition - proposerPosition) - 1 <= targetDistance) {
                        return false;
                    }
            }
        }

        return true;
    }

    private void permutation(char[] chars, int depth, int r) {
        if (depth == r) {
            StringBuilder answer = new StringBuilder();
            for (int i = 0; i < r; i++) {
                answer.append(chars[i]);
            }

            candidates.add(answer.toString());
            return;
        }

        for (int i = depth; i < chars.length; i++) {
            this.swap(chars, i, depth);
            this.permutation(chars, depth + 1, r);
            this.swap(chars, i, depth);
        }
    }

    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}

결과