Table of contents

프로그래머스 숫자야구

숫자야구 게임에 관련된 문제다. 질문한 세 자리의 수, 스트라이크의 수, 볼의 수를 담은 2차원 배열이 주어졌을 때, 가능한 답의 개수를 구해야 한다.

완전탐색에 분류된 이유는 가능한 모든 숫자를 검사해봐야 하기 때문이다. [1, 2, 3, 4, 5, 6, 7, 8, 9] 9개의 숫자 중 3개를 선택하여 배열한 수와 질문에 주어진 숫자를 비교하여 스트라이크와 볼이 같다면 해당 숫자배열이 가능한 정답이 된다. 123, 132 처럼 순서가 바뀌면 스트라이크와 볼이 달라지기 때문에 조합이 아닌 순열 문제이다.

순열과 조합 참고

입출력 예
baseball return
[[123, 1, 1], [356, 1, 0], [327, 2, 0], [489, 0, 1]] 2

입출력 예시를 살펴보자. 여기서 가능한 정답은 324와 328 이다.

[1, 2, 3, 4, 5, 6, 7, 8, 9] 9개의 숫자 중 3개를 선택한 순열의 목록과 [123, 356, 327, 489]를 비교한다. 각각의 비교에서 스트라이크와 볼이 같다면 해당하는 순열이 가능한 정답이 된다.

@Test
public void testNumberBaseball() {
    solution(new int[][]{
        {123, 1, 1},
        {356, 1, 0},
        {327, 2, 0},
        {489, 0, 1},
    });
}

int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int result;

private int solution(int[][] baseball) {
    result = 0;
    permutation(baseball, 0, numbers.length, 3);
    return result;
}

private void permutation(int[][] baseball, int depth, int n, int r) {
    if (depth == r) {
        int[] data = new int[r];
        for (int i = 0; i < r; i++) {
            data[i] = numbers[i];
        }

        if (checkAll(baseball, data)) {
            result++;
        }
        return;
    }

    for (int i = depth; i < n; i++) {
        swap(numbers, depth, i);
        permutation(baseball, depth + 1, n, r);
        swap(numbers, depth, i);
    }
}

private void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}


private boolean checkAll(int[][] baseball, int[] target) {
    for (int i = 0; i < baseball.length; i++) {
        int s = baseball[i][1];
        int b = baseball[i][2];

        int[] baseballNumber = new int[3];
        baseballNumber[2] = baseball[i][0] % 10;
        baseballNumber[1] = baseball[i][0] / 10 % 10;
        baseballNumber[0] = baseball[i][0] / 100;

        if (!check(baseballNumber, target, s, b)) {
            return false;
        }
    }
    return true;
}

@Test
public void testCheck() {
    assertThat(check(new int[]{4, 5, 6}, new int[]{7, 4, 6}, 1, 1)).isTrue();
    assertThat(check(new int[]{4, 5, 6}, new int[]{4, 6, 5}, 1, 2)).isTrue();
    assertThat(check(new int[]{4, 5, 6}, new int[]{4, 5, 6}, 3, 0)).isTrue();


    assertThat(check(new int[]{4, 5, 6}, new int[]{4, 5, 6}, 2, 1)).isFalse();
}

private boolean check(int[] numbers, int[] target, int s, int b) {
    int strike = 0;
    int ball = 0;

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (numbers[i] != target[j]) continue;

            if (i == j) strike++;
            else ball++;
        }
    }

    return s == strike && b == ball;
}

대부분 순열이나 조합 문제에는 효율성 테스트가 들어가지 않는 것 같다.