[ Lv 2 ] [ BackTracking ] 단체사진 찍기

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

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

 

풀이 과정

---

Python을 사용할 수 없어 Java로 풀이함!!

1. 주어진 data을 각각 인원1, 인원2, 연산, 거리 형식의 Op 클래스로 치환한다.
2. Op 클래스에서는 거리가 주어졌을 때, 연산 결과가 반환되는 operate 메소드를 만들어 둔다.
3. 최대 인원수가 8명이므로 가능한 모든 순열을 Recursion으로 만들어 준다.
   
   1. Set 자료구조로는 현재 순열에 어떤 인원이 포함되어 있는지 체크
   2. Map 자료구조로는 현재 인원의 위치를 저장
   3. 이후 Op 클래스의 operate 메소드를 호출할 때 Map 자료구조를 넘겨줌으로써 빠르게 거리계산이 가능하도록 한다.
4. 각각의 순열에 대해서 모든 Op클래스의 operate 메소드가 True가 나온다면 카운팅 해주고, 하나라도 False가 나온다면 카운팅 해주지 않는다.
5. 카운팅 개수를 리턴해주면 끝

---

소스 코드

---

 

import java.util.HashSet;
import java.util.HashMap;
import java.util.Arrays;

class Op{
    private char from;
    private char to;
    private char operation;
    private int dist;

    public Op(String data) {
        this.from = data.charAt(0);
        this.to = data.charAt(2);
        this.operation = data.charAt(3);
        this.dist = data.charAt(4) - '0';
    }
    
    public void print() {
         System.out.println(this.from + "//" + this.to);
    }

    public boolean execute(HashMap<Character, Integer> pos) {
        int distance = Math.abs(pos.get(from) - pos.get(to)) - 1;
        if (operation == '=') {
            return distance == dist;
        }
        if (operation == '>') {
            return distance > dist;
        }
        if (operation == '<') {
            return distance < dist;
        }
        return false;
    }
}

class Solution {
    private HashMap<Character, Integer> characterPos = new HashMap<>();
    private HashSet<Character> character = new HashSet<>();
    private static final Character[] CHARACTER = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    private int caseCount = 0;
    private Op[] operations;

    public void solve(int index) {
        if (index == 9) {
            if (check(characterPos)) {
                caseCount++;
            }
            return;
        }

        for (int i = 0; i < CHARACTER.length; i++) {
            if (!character.contains(CHARACTER[i])) {
                character.add(CHARACTER[i]);
                characterPos.put(CHARACTER[i], index);
                solve(index + 1);
                character.remove(CHARACTER[i]);
            }
        }
    }

    public boolean check(HashMap<Character, Integer> pos) {
        for (Op operation : operations) {
            if (!operation.execute(pos)) {
                return false;
            }
        }
        return true;
    }

    public int solution(int n, String[] data) {
        operations = Arrays.stream(data)
                .map(op -> new Op(op))
                .toArray(size -> new Op[size]);
        solve(1);
        return caseCount;
    }
}