[lv2] 단체사진 찍기

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

 

구현 문제

 

문제에서 조합으로 8명의 친구들을 뽑는 경우의 수는 8! = 40320이므로,

조합으로 일단 뽑고 100개의 조건을 모든 조합에 대해 판별해도 시간이 널널하다.

 

특이 사항

전역변수로 answer을 선언하면, solution 메서드 스코프에서 answer  변수 초기화를 해줘야한다. 아니면 오답을 받는다.

(프그스 풀면서 처음 보는 패턴이었다;;)

https://school.programmers.co.kr/questions/13442

 

class Solution {

  static int answer, F = 8, D;
  static char[] pick = new char[F], frd = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
  
  static boolean[] vst = new boolean[F];
  static String[] data;

  public int solution(int n, String[] data) {
    answer = 0;
    this.data = data;
    D = data.length;

    permu(0);

    return answer;
  }

  // 8! = 40320
  static void permu(int dep) {
    if (dep == F) {

      if (isMatched(pick)) {
        answer++;
      }

      return;
    }

    for (int i = 0; i < F; i++) {
      if (!vst[i]) {
        vst[i] = true;
        pick[dep] = frd[i];
        permu(dep + 1);
        vst[i] = false;
      }
    }

  }

  static boolean isMatched(char[] pick) {

    for (int i = 0; i < D; i++) {
      String con = data[i];

      int fromIdx = -1;
      int toIdx = -1;

      for (int j = 0; j < F; j++) {
        if (pick[j] == con.charAt(0)) {
          fromIdx = j;
        }
        if (pick[j] == con.charAt(2)) {
          toIdx = j;
        }
      }

      int dis = Math.abs(fromIdx - toIdx) - 1;
      int matchedDis = con.charAt(4) - '0';

      char sign = con.charAt(3);

      if (sign == '=' && dis != matchedDis) {
        return false;
      } else if (sign == '<' && dis >= matchedDis) {
        return false;
      } else if (sign == '>' && dis <= matchedDis) {
        return false;
      }
    }

    return true;
  }
}