[알고리즘]BabyGin 판단 문제(순열 사용)

0~9사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때, 3장의 카드가 연속적인 번호를 갖는 경우를 run으로 정의하고,

3장의 카드가 동일한 번호를 갖는 경우를 triplete로 정의한다

또한,6장의 카드가 run과 triplete로만 구성된 경우를 baby-gin으로 부른다

 

ex) 667767은 두개의 triplete이므로 baby-gin이다(666,777)

054060은 한개의 run과 한개의 triplete이므로 역시 baby-gin이다(456,000)

101123은 한개의 triplete가 존재하나,023이 run이 아니므로 baby-gin이 아니다

import java.util.*;

public class AlgoTask3 {
	int[] arr=new int[6];
	int baby=0;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		AlgoTask3 at=new AlgoTask3();
		at.ranCard(sc);
	}
	public void ranCard(Scanner sc) {
			
		for(int i=0;i<6;i++) {
			System.out.println("0~9사이의 숫자를 입력하시오"+(i+1)+"번째카드");
			int num=sc.nextInt();
			if(num>9) {
				System.out.println("0~9사이 입력바람");
				i--;
				continue;
			}else {
				arr[i]=num;
			}
		}
		
		perm(arr,0);
		if(baby>=1) {
			System.out.println("babygin");
		}else {
			System.out.println("not");
		}
	}
	public void perm(int [] arr,int depth) { //순열알고리즘을 사용하여 완전탐색을 한다(이 6자리 숫자들로 조합할수있는 모든 숫자 탐색)
		int run = 0,triplete=0;
		if(depth==6) {// 그 깊이가 6 즉 모든 6개 숫자를 다 사용해서 조합했을 경우
			if(arr[0]==arr[1]&&arr[1]==arr[2]) {//triplete 맨앞 3숫자 동일경우
				triplete++;
			}
			if(arr[3]==arr[4]&&arr[4]==arr[5]) {//triplete 그다음 3숫자가 동일한 경우
				triplete++;
			}
			if(arr[0]+1==arr[1]&&arr[1]+1==arr[2]) {//run 맨앞자리 3자리가 연속된수인경우 ex) 123456 이라 치면 (n1)+1==(n2)&& (n2)+1== (n3) 연속된 수 패턴임 
				run++;
			}
			if(arr[3]+1==arr[4]&&arr[4]+1==arr[5]) {//run 그다움 3자리가 연속된 수
				run++;
			}
			if(run==2||run+triplete==2||triplete==2) {//run이 2개이거나 run+triplete이 2개이거나 triplete이 2개일경우 베이비진 성립
				baby++;	
			}
			run=0;
			triplete=0;
			return;
		}
		for(int i=depth;i<6;i++) { 
			swap(arr,depth,i);
			perm(arr,depth+1);
			swap(arr,depth,i);
		}
		
	}	
	public void swap(int []arr,int depth,int i) {
		int temp=arr[depth];
		arr[depth]=arr[i];
		arr[i]=temp;		
	}	
}

순열을 좀더 깊게 파서 알고리즘을 정확히 숙지해야 할것 같다.. 이번주말 헬 예상이다..

 

 

참고:https://bcp0109.tistory.com/14