728x90
목차
완전 검색
가능한 모든 경우의 수를 확인하는 기법
Brute-force, Generate-and-Test 기법
경우의 수가 작을 때 유용함
정확성은 높지만, 경우의 수가 커진다면 비효율적일 수 있음
Baby-Gin
임의의 숫자 6개를 뽑아 run과 triplet으로만 구성된 카드 = baby-gin
- run: 3장의 카드가 연속적인 번호를 갖는 경우
- triplet: 3장의 카드가 동일한 번호를 갖는 경우
모든 경우의 수 구하기 (순열)
6개의 숫자는 6!개의 순열이 가능
- 먼저 6개 숫자에서 가능한 세 자리 순열(6P3)을 구하여 run 또는 triplet에 해당하는지 검사
- true를 반환한다면, 다시 남은 3가지 수 중에서 순열을 구하여 run 또는 triplet에 해당하는지 검사
for (int i = 0; i < arr.length; i++) {
int i1 = arr[i]; // 첫 번째 자리
for (int j = 0; j < arr.length; j++) {
if (j != i) {
int i2 = arr[j]; // 두 번째 자리
for (int k = 0; k < arr.length; k++) {
if (k != i && k != j) {
int i3 = arr[k]; // 세 번째 자리
int num = i1 * 100 + i2 * 10 + i3; // run과 triplet을 체크할 세 자리 수
if (isRun(num) || isTriplet(num)) { // 이 수가 해당한다면
for (int l = 0; l < arr.length; l++) {
if (l != i && l != j && l != k) {
int o1 = arr[l]; // 네 번째 자리
for (int m = 0; m < arr.length; m++) {
if (m != i && m != j && m != k && m != l) {
int o2 = arr[m]; // 다섯 번째 자리
for (int n = 0; n < arr.length; n++) {
if (n != i && n != j && n != k && n != l && n != m) {
int o3 = arr[n]; // 여섯 번재 자리
int other = o1 * 100 + o2 * 10 + o3;
if (isRun(other) || isTriplet(other)) {
return true;
}
}
}
}
}
}
}
}
}
}
}
}
}
run 확인
정렬 후 값들의 차이가 1이면 true
static boolean isRun(int N) {
ArrayList<Integer> run = new ArrayList<>();
int i1 = N / 100;
int i2 = (N / 10) % 10;
int i3 = (N % 10) % 10;
run.add(i1);
run.add(i2);
run.add(i3);
Collections.sort(run);
if (run.get(1) - run.get(0) == 1 && run.get(2) - run.get(1) == 1) {
return true;
}
return false;
}
triplet 확인
세 수가 같으면 true 반환
static boolean isTriplet(int N) {
int i1 = N / 100;
int i2 = (N / 10) % 10;
int i3 = (N % 10) % 10;
if (i1 == i2 && i2 == i3) {
return true;
}
return false;
}
전체 코드
package search;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class ExhaustiveSearch_babygin {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr = new int[6];
for (int i = 0; i < 6; i++) {
arr[i] = sc.nextInt();
}
System.out.println(makePermut(arr));
}
static boolean makePermut(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int i1 = arr[i];
for (int j = 0; j < arr.length; j++) {
if (j != i) {
int i2 = arr[j];
for (int k = 0; k < arr.length; k++) {
if (k != i && k != j) {
int i3 = arr[k];
int num = i1 * 100 + i2 * 10 + i3;
if (isRun(num) || isTriplet(num)) {
for (int l = 0; l < arr.length; l++) {
if (l != i && l != j && l != k) {
int o1 = arr[l];
for (int m = 0; m < arr.length; m++) {
if (m != i && m != j && m != k && m != l) {
int o2 = arr[m];
for (int n = 0; n < arr.length; n++) {
if (n != i && n != j && n != k && n != l && n != m) {
int o3 = arr[n];
int other = o1 * 100 + o2 * 10 + o3;
if (isRun(other) || isTriplet(other)) {
return true;
}
}
}
}
}
}
}
}
}
}
}
}
}
return false;
}
static boolean isRun(int N) {
ArrayList<Integer> run = new ArrayList<>();
int i1 = N / 100;
int i2 = (N / 10) % 10;
int i3 = (N % 10) % 10;
run.add(i1);
run.add(i2);
run.add(i3);
Collections.sort(run);
if (run.get(1) - run.get(0) == 1 && run.get(2) - run.get(1) == 1) {
return true;
}
return false;
}
static boolean isTriplet(int N) {
int i1 = N / 100;
int i2 = (N / 10) % 10;
int i3 = (N % 10) % 10;
if (i1 == i2 && i2 == i3) {
return true;
}
return false;
}
}
728x90
'CS > Algorithm' 카테고리의 다른 글
[알고리즘] 삽입 정렬 Insertion Sort (자바/Java) (0) | 2022.08.17 |
---|---|
[알고리즘] 카운팅 정렬(Counting Sort) (자바/Java) (0) | 2022.08.10 |
[알고리즘] 검색 Search - 순차 검색, 이진 검색 (자바/Java) (0) | 2022.08.08 |
[알고리즘] 정렬 - 선택 정렬(Selection Sort) (자바/Java) (0) | 2022.08.08 |
[알고리즘] 정렬 - 버블 정렬(Bubble Sort) (자바/Java) (0) | 2022.08.08 |