🔗 Group Photo

In the fall, the Kakao Friends went on a group outing. After having a great time, they lined up in a row in front of the camera to take a group photo at the end. However, since everyone wanted a different arrangement, it took a long time to decide the order to stand in. Neo wanted to stand next to Prodo, and Ryan, who had once been hit by fire breathed by Tube, wanted to stand at least three spots away from Tube. On the way back after taking the picture, Muzi got to wondering whether there might have been other ways to stand that also satisfied everyone's conditions. Let's write a program that computes the number of ways everyone can stand in a row that satisfies each Friend's desired conditions, given those conditions as input.

The input is given as an integer n representing the number of conditions, and a string array data consisting of n elements. Each element of data is a string in a form like N~F=0, representing each Friend's desired condition. The constraints are as follows.

• 1 <= n <= 100
• Each element of data is a string consisting of five characters. The condition of each element is as follows.
  • The first and third characters are each one of the following 8: { A, C, F, J, M, N, R, T }, representing Apeach, Con, Frodo, Jay-G, Muzi, Neo, Ryan, and Tube, respectively. The first character is the Friend proposing the condition, and the third character is the counterpart. The first and third characters are always different.
  • The second character is always ~.
  • The fourth character is one of the following 3: { =, <, > }, representing equal to, less than, and greater than, respectively.
  • The fifth character is a digit character representing an integer from 0 to 6, inclusive, indicating the gap specified in the condition. Here, the gap is the number of other Friends standing between the two Friends.

Return the number of arrangements that satisfy all the conditions.

The first example is as described in the problem: Neo wants a gap of 0 with Frodo, and Ryan wants a gap greater than 2 with Tube.

The second example describes a situation where Muzi wants a gap less than 2 with Con, while, conversely, Con wants a gap greater than 1 with Muzi. Since these conditions can't be satisfied simultaneously, the number of arrangements is 0.

We need to find the number of arrangements in which the Kakao Friends can stand in a row for a photo while satisfying everyone's desired conditions.

Since the arrangement (order) matters here, permutations are the right approach.

Implement a permutation algorithm to enumerate every possible arrangement, and for each arrangement, compare it against the conditions and count only the ones that satisfy them.

JAVA
private void permutation(String[] output, boolean[] isVisit, int depth, int n, String[] data)
{
	// If we've reached the end
	if (depth == NAMES.length)
	{
		answer += isValidate(n, data, output) ? 1 : 0;
		
		return;
	}
	
	for (int i = 0; i < NAMES.length; i++)
	{
		// If not visited yet
		if (!isVisit[i])
		{
			isVisit[i] = true;
			
			output[depth] = NAMES[i];
			
			permutation(output, isVisit, depth + 1, n, data);
			
			isVisit[i] = false;
		}
	}
}

The implemented permutation algorithm looks like the above.

Once all arrangements have been computed, the isValidate method determines whether the conditions match.

If even one of the given conditions doesn't match, it returns false; if all conditions have been checked with no issue, it returns true.

JAVA
/**
 * Group Photo class
 *
 * @author RWB
 * @since 2021.12.26 Sun 20:35:07
 */
class Solution
{
	private static final String[] NAMES = { "A", "C", "F", "J", "M", "N", "R", "T" };
	private int answer;
	
	/**
	 * Method that returns the answer
	 *
	 * @param n: [int] number of conditions
	 * @param data: [String[]] conditions
	 *
	 * @return [int] answer
	 */
	public int solution(int n, String[] data)
	{
		answer = 0;
		
		int count = NAMES.length;
		
		String[] output = new String[count];
		
		boolean[] isVisit = new boolean[count];
		
		permutation(output, isVisit, 0, n, data);
		
		return answer;
	}
	
	/**
	 * Permutation method
	 *
	 * @param output: [String[]] array storing the result
	 * @param isVisit: [boolean[]] array of visited flags
	 * @param depth: [int] counter
	 * @param data: [String[]] conditions
	 * @param n: [int] number of conditions
	 */
	private void permutation(String[] output, boolean[] isVisit, int depth, int n, String[] data)
	{
		// If we've reached the end
		if (depth == NAMES.length)
		{
			answer += isValidate(n, data, output) ? 1 : 0;
			
			return;
		}
		
		for (int i = 0; i < NAMES.length; i++)
		{
			// If not visited yet
			if (!isVisit[i])
			{
				isVisit[i] = true;
				
				output[depth] = NAMES[i];
				
				permutation(output, isVisit, depth + 1, n, data);
				
				isVisit[i] = false;
			}
		}
	}
	
	/**
	 * Method that returns the condition validation result
	 *
	 * @param n: [int] number of conditions
	 * @param data: [String[]] conditions
	 * @param output: [String[]] array storing the result
	 *
	 * @return [boolean] condition validation result
	 */
	private boolean isValidate(int n, String[] data, String[] output)
	{
		StringBuilder builder = new StringBuilder();
		
		for (String out : output)
		{
			builder.append(out);
		}
		
		String text = builder.toString();
		
		for (int i = 0; i < n; i++)
		{
			String[] temp = data[i].split("");
			
			String name1 = temp[0];
			String name2 = temp[2];
			String operation = temp[3];
			
			int distance = Integer.parseInt(temp[4]);
			
			int realDistance = Math.abs(text.indexOf(name1) - text.indexOf(name2)) - 1;
			
			// If it doesn't match the > condition
			if (operation.equals(">") && realDistance <= distance)
			{
				return false;
			}
			
			// If it doesn't match the = condition
			else if (operation.equals("=") && realDistance != distance)
			{
				return false;
			}
			
			// If it doesn't match the < condition
			else if (operation.equals("<") && realDistance >= distance)
			{
				return false;
			}
		}
		
		return true;
	}
}