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

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

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

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

풀이 : BackTracking을 이용하여 해당 조건에 해당되는 경우를 체크한다.

import java.util.*;

class Solution {

   static char[] cha = { 'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T' }; // 회원
   static char[] position = new char[8];
   static boolean[] check = new boolean[8];
   static int ans; // 전체 변수

  public int solution(int n, String[] data) {
      ans = 0; // 변수 초기화 필수
      bt(0, n, data); // BackTracking
      return ans;
  }

  public static void bt(int idx, int n, String[] data) {
		if (idx == 8) {
			if (possible(n, data)) ans++; // 조건 체크
			return;
		}

		for (int i = 0; i < 8; i++) {
			if (!check[i]) {
				check[i] = true;
				position[idx] = cha[i];
				bt(idx + 1, n, data);
				check[i] = false;
			}
		}

	}
    private static boolean possible(int n, String[] data) {
		for(String str : data) {
			int a = 0, b = 0;
			char oper = str.charAt(3);
			int num = str.charAt(4) - '0';
			for (int i = 0; i < 8; i++) {
				if(position[i] == str.charAt(0)) a = i;
				if(position[i] == str.charAt(2)) b = i;
			}
			int gap = Math.abs(a-b)-1;
			switch (oper) {
			case '=':
				if(gap != num) return false;
				break;
			case '<':
				if(gap >= num) return false;
				break;
			case '>':
				if(gap <= num) return false;
				break;
			}
		}
		return true;
	}
  }