[프로그래머스] 단체사진 찍기 (2017 카카오코드 본선) - Java

문제

단체사진 찍기 (2017 카카오코드 본선)

프로그래머스

 

아이디어

배열 길이(카카오프렌즈 수)가 8밖에 되지 않기 때문에 순열을 사용한 완전 탐색으로 풀 수 있었다.

1. 가능한 모든 경우의 수를 순열을 통해 구해 놓은 뒤,
2. 주어진 조건에 일치할 경우만 카운트 한다.

 

전체 코드

import java.util.*;

class Solution {
    List<String> list;
    char[] arr = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    int N;
    char[] sel;
    boolean[] visited;
    
    void permutation(int L) {
        if (L == N) {
            list.add(String.valueOf(sel));
            return;
        }
        for (int i=0; i<N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                sel[L] = arr[i];
                permutation(L+1);
                visited[i] = false;
            }
        }
    }
    
    public int solution(int n, String[] data) {
        int answer = 0;
        N = 8;
        sel = new char[N];
        visited = new boolean[N];
        list = new ArrayList<>();
        
        permutation(0);
        answer = list.size();
        
        for (String s: list) {
            for (int i=0; i<n; i++) {
                char a = data[i].charAt(0);
                char b = data[i].charAt(2);
                char cond = data[i].charAt(3);
                int num = data[i].charAt(4) - '0';
                
                if (cond == '=' && Math.abs(s.indexOf(a) - s.indexOf(b))-1 == num) continue; 
                if (cond == '>' && Math.abs(s.indexOf(a) - s.indexOf(b))-1 > num) continue;
                if (cond == '<' && Math.abs(s.indexOf(a) - s.indexOf(b))-1 < num) continue;
                answer--;
                break;
            }
        }
        
        return answer;
    }
}