[2017 카카오코드 본선] 단체사진 찍기

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

프로그래머스

 

파이썬

answer = 0


def permute(names, visited: set, data):
    global answer
    if len(names) == 8:
        if check(names, data):
            answer += 1
        return
    for name in 'ACFJMNRT':
        if name not in visited:
            visited.add(name)
            permute(names + name, visited, data)
            visited.remove(name)


def check(names, data):
    for datum in data:
        distance1 = abs(names.index(datum[0]) - names.index(datum[2])) - 1
        distance2 = int(datum[4])
        op = datum[3]
        if op == '=' and distance1 != distance2:
            return False
        elif op == '>' and distance1 <= distance2:
            return False
        elif op == '<' and distance1 >= distance2:
            return False
    return True


def solution(n, data):
    permute("", set(), data)
    return answer


# print(solution(2, ["N~F=0", "R~T>2"]))

재귀를 이용해 순열을 만들어 본 적이 있다면 
어렵지 않을 겁니다. 

https://comdoc.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9

 

자바

파이썬 느낌으로..

import java.util.*;

class Solution {
    static int answer;
    static char[] friends = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};

    public int solution(int n, String[] data) {
        answer = 0;
        permute("", new HashSet<>(), data);
        return answer;
    }

    static void permute(String names, HashSet<Character> visited, String[] data) {
        if (names.length() == 8) {
            if (check(names, data)) {
                answer++;
            }
            return;
        }
        for (var name : friends) {
            if (!visited.contains(name)) {
                visited.add(name);
                permute(names + name, visited, data);
                visited.remove(name);
            }
        }
    }

    static boolean check(String names, String[] data) {
        for (String datum : data) {
            var op = datum.charAt(3);
            var distance1 = Math.abs(names.indexOf(datum.charAt(0)) - names.indexOf(datum.charAt(2))) - 1;
            var distance2 = datum.charAt(4) - '0';
            if (op == '=' && distance1 != distance2) return false;
            else if (op == '>' && distance1 <= distance2) return false;
            else if (op == '<' && distance1 >= distance2) return false;
        }
        return true;
    }
}

테스트 1 〉	통과 (1938.67ms, 383MB)

속도를 고려해서.. 

class Solution {
    static int answer;
    static String friends = "ACFJMNRT";

    public int solution(int n, String[] data) {
        answer = 0;
        permute(0, new int[8], new boolean[8], data);
        return answer;
    }

    void permute(int index, int[] names, boolean[] visited, String[] data) {
        if (index == 8) {
            if (check(names, data)) answer++;
            return;
        }
        for (var i = 0; i < 8; i++) {
            if (!visited[i]) {
                visited[i] = true;
                names[index] = i;
                permute(index + 1, names, visited, data);
                visited[i] = false;
            }
        }
    }

    boolean check(int[] names, String[] data) {
        for (String datum : data) {
            var distance1 =
                    Math.abs(names[friends.indexOf(datum.charAt(0))] - names[friends.indexOf(datum.charAt(2))]) - 1;
            var distance2 = datum.charAt(4) - '0';
            var op = datum.charAt(3);

            if (op == '=' && distance1 != distance2) return false;
            else if (op == '>' && distance1 <= distance2) return false;
            else if (op == '<' && distance1 >= distance2) return false;
        }
        return true;
    }
}

테스트 1 〉	통과 (604.34ms, 91.5MB)