문제 링크

문제 간단 해석

순열을 생성하고 조건을 따져 특정 값들을 필터링하는 문제.
BFS로 풀어도 되긴 하지만.. 막상 해봤더니 너무 느리고 비효율적이더라.
따라서 DFS로 해결.

풀이 코드

import java.util.Map;
import java.util.HashMap;

class Solution {
    private String[] data;
    private int answer = 0;
    private final char[] ch = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    private final Map<Character, Integer> map = new HashMap<>();
    
    public void dfs(int repeat) {
        if (repeat == 8) {
            int A, B, area, num;
            
            for (String d: data) {
                A = map.get(d.charAt(0));
                B = map.get(d.charAt(2));
                area = Math.abs(A - B) - 1;
                num = d.charAt(4) - '0';

                switch(d.charAt(3)) {
                    case '=':
                        if (area != num)
                            return;
                        break;
                    case '>':
                        if (area <= num)
                            return;
                        break;
                    case '<':
                        if (area >= num)
                            return;
                        break;
                    default:
                        break;
                }

            }
            answer++;
            return;
        }
        
        for (int i = 0; i < 8; i++) {
            if (!map.containsKey(ch[i])) {
                map.put(ch[i], repeat);
                dfs(repeat + 1);
                map.remove(ch[i]);
            }
        }
    }
    
    public int solution(int n, String[] data) {
        this.data = data;
        dfs(0);
        return answer;
    }
}

해석

private String[] data;
private int answer = 0;
private final char[] ch = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
private final Map<Character, Integer> map = new HashMap<>();

처음에 주입받을 data, 답을 카운트할 answer, 캐릭터들의 ch, 캐릭터들의 위치를 기록할 map을 선언했다.

public int solution(int n, String[] data) {
    this.data = data;
    dfs(0);
    return answer;
}

solution에서는 data를 먼저 주입하고, dfs 함수를 돌린 후 answer를 반환한다.

public void dfs(int repeat) {
    if (repeat == 8) {
        
        ...
        
        answer++;
        return;
    }

    for (int i = 0; i < 8; i++) {
        if (!map.containsKey(ch[i])) {
            map.put(ch[i], repeat);
            dfs(repeat + 1);
            map.remove(ch[i]);
        }
    }
}

repeat이 8이 됐을 때와, 그렇지 않을 때를 나눴다.
8이 되기 전까진, map에 캐릭터와 자리값을 주입한다.
해당 캐릭터가 이미 자리를 잡았다면 건너뛰고, 아니라면 repeat 횟수에 맞는 자리를 지정해준다.
그 후 재귀를 통해 다음 자리를 지정한다.
재귀가 끝나 다시금 원래 함수로 왔다면, map에서 해당 캐릭터를 제거해 자리를 비운 후 다른 캐릭터를 넣어준다.

public void dfs(int repeat) {
    if (repeat == 8) {
        int A, B, area, num;

        for (String d: data) {
            A = map.get(d.charAt(0));
            B = map.get(d.charAt(2));
            area = Math.abs(A - B) - 1;
            num = d.charAt(4) - '0';

            switch(d.charAt(3)) {
                case '=':
                    if (area != num)
                        return;
                    break;
                case '>':
                    if (area <= num)
                        return;
                    break;
                case '<':
                    if (area >= num)
                        return;
                    break;
                default:
                    break;
            }

        }
        answer++;
        return;
    }

    ...
    
}

8이 되었을 때에는, 모든 캐릭터가 자리를 잡은 상태이다.
따라서 data를 foreach로 하나씩 가져온 후 조건을 비교한다.
A와 B는 조건에 선언된 캐릭터들이다.
area는 두 캐릭터의 거리이다.
num은 조건에 선언된 거리이다.

조건이 =, >, <에 따라 각자 확인해야 할 범위가 다르므로 switch를 통해 판별하도록 했다.

=일 때, 두 캐릭터의 거리와 조건에 선언된 거리가 다르다면 경우의 수(map)과 해당 조건이 불일치하므로 return을 통해 다른 경우의 수를 찾게 한다.
>, <도 마찬가지.
모든 조건을 통과한 경우의 수일 때만 answer를 늘리고 종료하게끔 했다.

여담

비효율적이지만.. BFS도 푼 게 아까워 일단 올려본다.

import java.util.Map;
import java.util.HashMap;
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int solution(int n, String[] data) {
        Queue<Map<Character, Integer>> queue = new LinkedList<>();
        queue.add(new HashMap<>());
        Map<Character, Integer> map, clone;
        char[] ch = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
        int limit, A, B, area, num, answer = 0;

        for (int i = 0; i < 8; i++) {
            limit = queue.size();

            for (int j = 0; j < limit; j++) {
                map = queue.poll();

                for (int c = 0; c < 8; c++) {
                    if (map.containsKey(ch[c]))
                        continue;

                    clone = new HashMap<>(map);
                    clone.put(ch[c], i);
                    queue.add(clone);
                }
            }
        }

        check: while (!queue.isEmpty()) {
            map = queue.poll();

            for (String d: data) {
                A = map.get(d.charAt(0));
                B = map.get(d.charAt(2));
                area = Math.abs(A - B) - 1;
                num = d.charAt(4) - '0';

                switch(d.charAt(3)) {
                    case '=':
                        if (area != num)
                            continue check;
                        break;
                    case '>':
                        if (area <= num)
                            continue check;
                        break;
                    case '<':
                        if (area >= num)
                            continue check;
                        break;
                    default:
                        break;
                }

            }
            answer++;
        }

        return answer;
    }
}

속도 차이는 한 3~4배정도? 아무래도 queue로 계속 데이터를 관리하다보니 느릴 수 밖에 없는 것 같다.