[2017 카카오코드]단체사진 찍기

📍 문제 설명

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

코딩테스트 연습 - 단체사진 찍기

 

💡 접근

범위가 크지않아 순열 문제로 접근은 했으나 data에 따라서 걸러주는데에서 시간이 꽤나 걸렸다.

처음에는 순열을 뽑을 때 처음에는 인덱스 번호나 프렌즈의 이름을 넣어줬는데,

인덱스 번호나 프렌즈의 이름만으로는 각 프렌즈의 인덱스 번호를 찾기가 비효율적이라 맵을 사용했다.

맵에 프렌즈의 이름과 프렌즈의 번호를 넣어두고 data에 있는 프렌즈의 이름으로 맵에 있는 프렌즈의 인덱스 번호를 구해서 그 인덱스 번호로 현재 뽑은 순열의 인덱스 번호를 구해서 그 둘의 차를 구했다.

 

그리고 거리가 1일 때 인덱스의 차이가 1이 아닌데 그 부분에서도 시간이 소요됐다.

 

👩‍💻 코드

import java.util.*;

class Solution {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static char[] c = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    static int[] arr;
    static HashMap<Character, Integer> map;
    static boolean[] visited;
    static String[] clone;
    static int answer;

    public int solution(int n, String[] data) {
        clone = data;
        visited =  new boolean[8];
        arr = new int[8];
        map = new HashMap<>();
        answer = 0;
        
        map.put('A',0);
        map.put('C',1);
        map.put('F',2);
        map.put('J',3);
        map.put('M',4);
        map.put('N',5);
        map.put('R',6);
        map.put('T',7);

        DFS(0);
        System.out.println(answer);
        return answer;
    }

    private void DFS(int L) {
        if (L == 8) {
            //8명을 세우는 경우의 수 중에서 data에 맞는 것만 뽑아내기
            if(check()) answer++;
            return;
        } else {
            for (int i = 0; i < 8; i++) {
                if(!visited[i]) {
                    visited[i] = true;
                    arr[L] = i;
                    DFS(L + 1);
                    visited[i] = false;
                }
            }
        }
    }

    private boolean check() {
        //arr[0] = A , arr[1] = C , arr[2] = F
        //data에 따라서 걸러주기
        for(String s : clone) {
            int a = arr[map.get(s.charAt(0))]; //N
            int b = arr[map.get(s.charAt(2))]; //F
            char op = s.charAt(3); //=
            int num = s.charAt(4) - '0' + 1;//0

            //차이가 num+1여야야함
            if(op == '=') {
                if(Math.abs(a-b) != num) return false;
            }
            //차이가 num 초과해야함 num 이하면 안됨
            else if(op == '>') {
                if(Math.abs(a-b) <= num) return false;
            }
            //차이가 num 미만이여야함 num 이상이면 안됨
            else if(op == '<') {
                if(Math.abs(a-b) >= num) return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution s = new Solution();

        int n = 2;
        String[] data = {"N~F=0", "R~T>2"};
        //String[] data = {"M~C<2", "C~M>1"};
        s.solution(n, data);
    }

}