[SWEA][S/W 문제해결 응용] Baby Gin (완전탐색 - 순열 이용)

문제

3, 4, 5와 같이 연속된 세 수가 1 차이로 등차일 경우를 Run이라 칭하고, 7, 7, 7와 같이 같은 수가 세 번 연속된 수를 Triplet이라고 한다. 

여섯개의 숫자 중, 3개는 Run, 3개는 Triplet을 이룰 때 Baby Gin이라고 한다. 여섯 개의 수가 주어졌을 때 Baby Gin임을 판별하는 알고리즘을 작성하시오.

 

 

 

풀이

 

import java.util.*;
 
public class Main {
    //Baby Gin 문제
    static int[] arr = {2,3,7,7,3,7};
    static boolean chk = false;
    
    //run 검사
    static boolean is_run(int st, int end) {
        if(Math.abs(arr[st]-arr[st+1])== 1 && Math.abs(arr[st]-arr[st+2])== 2)
            return true;
        return false;
    }
    //triplet 검사
    static boolean is_triplet(int st) {
        if(arr[st]==arr[st+1] && arr[st]==arr[st+2])
            return true;
        return false;
    }
    
    //교환 방식(순열 구하기)
    static void swap(int idx1, int idx2) {
        int tNum = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tNum;
    }
    public static void dfs_swap(int depth, int size) {
        if(depth == size && !chk) {
            if((is_run(0,2) && is_triplet(3))||
                    (is_run(3,5) && is_triplet(0))) {
                chk = true;
                for(int i=0;i<6;i++)
                    System.out.print(arr[i]);
                System.out.println();
            }
        }
        else {
            for(int i=depth;i<6;i++) {
                swap(depth,i);
                dfs_swap(depth+1,size);
                swap(depth,i);
            }
        }
    }
    
    public static boolean is_babygin(int[] arr) {
        dfs_swap(0,arr.length);
        return chk;
    }
    public static void main(String[] args) {
        System.out.println(is_babygin(arr));
    }
}