[프로그래머스] 단체사진 찍기

 

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

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

 

레벨2 문제이며, 경우의 수 계산하는 문제이고 백트래킹으로 해결할 수 있다.

백트래킹에 대한 특징은 재귀함수를 수행하면서 이전에 true 로 체크한 부분을 빠져나올 때는 false 로 바꿔야 한다는 것이다.

(ex. 예를 들면 방문에 대한 흔적)

백트래킹 과정에서 임계점을 설정 후, 이제 주어진 data 문자열 배열들을 체크하면서 하나의 조건이라도 만족하지 않을 경우 경우의 수에 계산하지 않도록 해야 한다.

 

아래는 예제 코드이며, 참고에 도움이 되길 바랍니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        int n = 2;
        String[] data = {"N~F=0", "R~T>2"};
        String[] data2 = {"M~C<2", "C~M>1"};
        System.out.println(solution(n,data));
        System.out.println(solution(n,data2));
    }

    static Map<String, Integer> indexMap;
    // 알파벳과 인덱스 숫자 맞추는 Map
    public static Map<String, Integer> init() {
        Map<String, Integer> map = new HashMap<>();

        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);
        return map;
    }
    
    // 원본 함수
    public static int solution(int n, String[] data) {
        int answer = 0;
        indexMap = init();
        answer = solve(0, null, null, data);
        return answer;
    }

    // 숫자 -> 알파벳 리턴
    public static String getAlpha(int index) {
        switch (index) {
            case 0:
                return "A";
            case 1:
                return "C";
            case 2:
                return "F";
            case 3:
                return "J";
            case 4:
                return "M";
            case 5:
                return "N";
            case 6:
                return "R";
            case 7:
                return "T";
        }
        return "";
    }

    // 백트래킹
    public static int solve(int count, int arr[], boolean[] visited, String[] data) {

        if (arr == null) arr = new int[8];
        if (visited == null) visited = new boolean[8];
        // 8 캐릭터에 대한 순열 계산 완료 시,
        if (count == 8) {
            // check logic
            boolean isSuccess = true;
            // 주어진 조건들 체크
            for (String condition : data) {
                if (!isSuccess) break;
                String source = Character.toString(condition.charAt(0));
                String target = Character.toString(condition.charAt(2));
                String operator = Character.toString(condition.charAt(3));
                int dis = Integer.parseInt(Character.toString(condition.charAt(4)));
                int s = indexMap.get(source);
                int t = indexMap.get(target);
                int s_index = -1;
                int t_index = -1;
                for (int i = 0; i < 8; i++) {
                    if (arr[i] == s) s_index = i;
                    if (arr[i] == t) t_index = i;
                }
                int diff = Math.abs(s_index - t_index) - 1;
                if (">".equals(operator)) {
                    if (diff <= dis) isSuccess = false;
                } else if ("<".equals(operator)) {
                    if (diff >= dis) isSuccess = false;
                } else {
                    if (diff != dis) isSuccess = false;
                }
            }
            // 주어진 조건 모두 만족 시 1 리턴, 그렇지 않으면 0
            return isSuccess == true ? 1 : 0;
        }
        int answer = 0;
        for (int i = 0; i < 8; i++) {
            if (visited[i] == false) {
                arr[count] = i;
                visited[i] = true;
                answer += solve(count+1, arr, visited,data);
                visited[i] = false;
            }
        }
        return answer;
    }


}