문제

SWEA_16546_Baby-gin

요약

0~9 사이의 숫자 6개가 주어질 때, 이 숫자들을 어떤 순서로 재배열하든 3장씩 묶었을 때 모두 같은 세 숫자(Triplet)이거나 연속된 세 숫자(Run)인 묶음 2개로 완전히 분할될 수 있는지 판별하는 문제

접근

이 문제는 주어진 6가지의 숫자로 만들 수 있는 모든 순열을 보고, Baby-gin이 되는지 파악하면 되는 문제다.

따라서 핵심은 순열을 구현하는 것!

알고리즘

• 순열 알고리즘

static isSelected[] : 해당 위치의 숫자의 선택 여부 저장
static numbers[] : 순열을 저장할 배열

void permutation(int cnt) { // cnt : 만들어진 순열의 길이
  if (cnt == N) {
      순열이 됐을 때 사용될 로직
      return
  }

  for (int i = 0; i < N; i++) {
      if (isSelected[i]) continue; // 이미 사용된 수 제외

      isSelected[i] = true;
      numbers[cnt] = i
      permutation(cnt + 1) // 다음 자리 채우기
      isSelected[i] = false; // 원상 복구 (백트래킹)
  }
}

제출코드

import java.io.*;
 
public class Solution {
    static int[] cards;
    static boolean res;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        int T = Integer.parseInt(br.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
            cards = new int[6];
            res = false;
 
            String str = br.readLine();
 
            for (int i = 0; i < 6; i++) {
                cards[i] = str.charAt(i) - '0';
            }
 
            permutation(0, new boolean[6], new int[6]);
            sb.append("#").append(tc).append(" ").append(res).append("\n");
        }
        System.out.print(sb.toString());
    }
 
    static void permutation(int cnt, boolean[] isSelected, int[] numbers) {
        if (cnt == 6) {
            // 0~2가 run? triple?
            boolean n1 = run(numbers[0], numbers[1], numbers[2]) || triple(numbers[0], numbers[1], numbers[2]);
            // 3~5가 run? triple?
            boolean n2 = run(numbers[3], numbers[4], numbers[5]) || triple(numbers[3], numbers[4], numbers[5]);
 
            if (n1 && n2) {
                res = true;
            }
            return;
        }
 
        for (int i = 0; i < 6; i++) {
            if (isSelected[i]) continue;
            isSelected[i] = true;
            numbers[cnt] = cards[i];
            permutation(cnt+1, isSelected, numbers);
            isSelected[i] = false;
            // permutation(cnt, isSelected, numbers); // 이건 굳이 다시 안해줘도 된다!
        }
    }
 
    static boolean run(int a, int b, int c) {
        return (b - a == 1) && (c - b == 1);
    }
 
    static boolean triple(int a, int b, int c) {
        return (a == b) && (b == c);
    }
}
 
/*
 
0~9까지 카드 중 임의 6장
3개가 연속 -> run
3개가 같은 번호 -> triple
 
6개가 run이랑 triple로 구성 -> baby gin
 
순열을 만들어서 확인해야한다!
 
// static
int[] cards = new int[6]
boolean res;
 
for(i = 0 ~ 6) {
    cards[i] = String.charAt(i)-'0'
}
res = false;
순열 코드
 
int cnt = 0;
isSelected[] = new boolean[6];
while(true) {
    if (cnt == 6);
    for (int i = 0; i < 6; i++) {
        isSelected[i] = true;
 
    }
}
 
void permutation(int cnt, boolean[] isSelected, int[] numbers) {
    if (cnt == 6) {
        // 0~2가 run? triple?
        boolean n1 = run(numbers[0], numbers[1], numbers[2]) || triple(numbers[0], numbers[1], numbers[2]);
        // 3~5가 run? triple?
        boolean n2 = run(numbers[3], numbers[4], numbers[5]) || triple(numbers[3], numbers[4], numbers[5]);
 
        if (n1 && n2) {
            res = true;
            return;
        }
    }
 
    for (int i = 0; i < 6; i++) {
        if (isSelected[i]) continue;
        isSelected[i] = true;
        numbers[cnt] = cards[i];
        permutation(cnt+1, isSelected, numbers);
        isSelected[i] = false;
        permutation(cnt, isSelected, numbers);
    }
}
 
boolean run(int a, int b, int c) {
    return (b - a == 1) && (c - b == 1);
}
 
boolean triple(int a, int b, int c) {
    return (a == b) && (b == c);
}
 
*/
 
// 여기까지 설계하는데 30분 사용! (16:29 ~ 17:02)
// 구현하는데 10분 사용! (17:08~17:19)

어려웠던 점

원상복구 한 다음에 다시 permutation을 호출했는데, 이건 하면 안된다!
다시 재귀를 부르게 되면 cnt는 계속 0이고 visited[0]은 false 상태여서 무한루프에 빠지게 된다!
부분집합을 만드는 코드와 헷갈렸다... 부분집합을 만들 때는 for 문을 사용하지 않는다!

• 재귀를 다시 한번 부르는 경우는 부분집합! why? 해당 수를 포함한다, 포함하지 않는다로 가지치기 때문!

순열에서 for문을 사용하는 이유는 순서가 중요하기 때문이다! 앞과 뒤의 순서가 중요하기 때문에 for를 0부터 계속 돌린다.

• 그렇다면 조합은?
  조합은 i를 start부터 돌린다. 왜? 앞쪽부터 만들 수 있는 조합을 다 만들어서 옮기니까, start값을 증가시키면서 모든 조합을 다 만들어버린다.

아직 순열을 완벽하게 다루는데엔 부족함이 있다. 관련 문제를 찾아서 푼다면 익숙해질 것 같다!

배운 점

numbers[] 배열과 isSelected[] 배열을 static으로 선언해도 된다!

• numbers[] : 순열의 값들이 바뀌면서 자연스레 값을 덮어쓰기 때문!
• isSelected[] : 재귀를 돈 후에 false로 상태 변환을 해주기 때문!

그래서 위의 permutation 함수를 아래와 같이 만들어도 된다.

static boolean[] isSelected
static int[] numbers
static void permutation(int cnt) {
		
    if (res) return; // 이미 베이비진이라면 즉시 종료

    if (cnt == 6) {
        // 0~2가 run? triple?
        boolean n1 = run(numbers[0], numbers[1], numbers[2]) || triple(numbers[0], numbers[1], numbers[2]);
        // 3~5가 run? triple?
        boolean n2 = run(numbers[3], numbers[4], numbers[5]) || triple(numbers[3], numbers[4], numbers[5]);

        if (n1 && n2) {
            res = true;
        }
        return;
    }

    for (int i = 0; i < 6; i++) {
        if (isSelected[i]) continue;
        isSelected[i] = true;
        numbers[cnt] = cards[i];
        permutation(cnt+1);
        isSelected[i] = false;
    }
}

문제를 풀 때, 설계에 사용된 시간, 직접 코드로 옮기는데 걸리는 시간을 측정하면서 진행하는건 좋은 습관인 것 같다! 앞으로도 이 방식으로 코딩테스트 연습을 해나가자!