[Kotlin] Korean Coding Test - Programmers - Taking a group photo

Question

Link

In the fall, Kakao Friends went on a picnic as a group. After having a good time, I stood side by side in front of the camera to take a group photo at the end. However, it took a long time to decide which order to set up because each wanted different arrangements. Neo wanted to stand alongside Frodo, and Ryan, who had been hit by a fire from the tube, wanted to stand at least three spaces away from the tube. On the way back from taking the picture, I wondered if there was a way to stand differently while satisfying the conditions everyone wanted. Let's write a program that calculates the number of cases in which each friend stands to satisfy all of the conditions when they receive the desired conditions as input.

The input is given as a string array data consisting of n integers and n elements representing the number of conditions. The element of data consists of a string in the form of N~F=0 in the condition desired by each friend.

Restrictions

1 <= n <= 100

The element of data is a five-letter string. The conditions for each element are as follows.

• The first and third letters are one of the following eight. {A, C, F, J, M, N, R, T} means Apeach, Con, Frodo, Jay-Z, Muji, Neo, Ryan, and Tube, respectively. The first letter is Friends who suggested the condition, and the third letter is the other person. The first and third letters are always different.
• The second letter is always ~.
• The fourth letter is one of the following three. {=, <, >} It means equal, less, and more than.
• The fifth character is an integer character type of 0 to 6, and means the interval presented in the condition. The interval is the number of other friends between the two friends.

Input/output example

Input/output example #1

• Input
• n: 2
• data: ["N~F=0", "R~T>2"]
• output: 3648

Input/output example #2

• Input
• n: 2
• ["M~C<2", "C~M>1"]
• output: 0

Solve

It is a permutation problem because we find a way to sort eight targets.

Because the number of input conditions is up to 100, and the number of all cases (8!) that align eight targets is not large, exhaustive search is used.

Code. Kotlin

class Solution {
    private val friends = "ACFJMNRT"
    private var answer = 0

    private fun solution(n: Int, data: Array<String>): Int {
        permutation(
            depth = 0,
            alignedFriends = Array(friends.length) { '_' },
            visited = Array(friends.length) { false },
            conditions = data
        )
        return answer
    }

    /**
     * Permutation
     * - Choose r from n different elements without duplication and list them in order.
     */
    private fun permutation(
        depth: Int,
        alignedFriends: Array<Char>,
        visited: Array<Boolean>,
        conditions: Array<String>
    ) {
        // Verify that conditions are satisfied after permutation processing is completed
        if (depth == friends.length) {
            if (check(conditions, alignedFriends)) answer++
            return
        }
        // permutation treatment
        for (i in friends.indices) {
            if (visited[i]) continue

            alignedFriends[depth] = friends[i]
            visited[i] = true
            permutation(depth + 1, alignedFriends, visited, conditions)
            visited[i] = false
        }
    }

    /**
     * Ensure that the conditions are met
     */
    private fun check(conditions: Array<String>, alignedFriends: Array<Char>): Boolean {
        conditions.forEach { condition ->
            val from = alignedFriends.indexOf(condition[0])
            val to = alignedFriends.indexOf(condition[2])
            val diff = abs(from - to)
            val interval = condition[4].toString().toInt() + 1
            when (condition[3]) {
                '>' -> if (diff <= interval) return false
                '<' -> if (diff >= interval) return false
                '=' -> if (diff != interval) return false
            }
        }
        return true
    }
}

No Kotlin submissions. Two I/O examples passed

Code. JAVA

class Solution {
    private String[] friends = {"A", "C", "F", "J", "M", "N", "R", "T"};
    private boolean[] visited;

    private int answer = 0;
        
    public int solution(int n, String[] data) {
        visited = new boolean[8];

        permutation("", data);

        return answer;
    }
    
    private void permutation(String alignedFriends, String[] conditions) {
        if (alignedFriends.length() == friends.length) {
            if (check(alignedFriends, conditions)) answer++;
            return;
        }
        for (int i = 0; i < friends.length; i++) {
            if (visited[i]) continue;

            visited[i] = true;
            permutation(alignedFriends + friends[i], conditions);
            visited[i] = false;
        }
    }

    private boolean check(String alignedFriends, String[] conditions) {
        for (String condition: conditions) {
            int start = alignedFriends.indexOf(condition.charAt(0));
            int end = alignedFriends.indexOf(condition.charAt(2));
            
            int diff = Math.abs(start - end);
            int interval = condition.charAt(4) - '0' + 1;
            
            char inequality = condition.charAt(3);
            if (inequality == '>') {
                if (diff > interval) continue;
            } else if (inequality == '<') {
                if (diff < interval) continue;
            } else if (inequality == '=') {
                if (diff == interval) continue;
            }
            return false;
        }
        return true;
    }
}

TEST 1 〉	Pass (1542.16ms, 378MB)

Kotlin Full Code Link