[프로그래머스]완전탐색 : 숫자 야구 (level 2)(java)

https://programmers.co.kr/learn/courses/30/lessons/42841

코딩테스트 연습 - 숫자 야구 | 프로그래머스

 

c++로 쓰여진 더 좋은 풀이글이 있습니다,,,

 

 

import java.util.ArrayList;
import java.util.List;
 
class Solution {
 
    public int[] arrNumbers;
    public List<int[]> listTestNumbers;
 
    public int solution(int[][] baseball) {
        listTestNumbers = new ArrayList<int[]>();
        arrNumbers = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 
        permutation(baseball, 0, 9, 3);
 
        // 만들어진 수가 모든 테스트케이스의 스트라이크와 볼 개수가 일치하면 answer +1
        int answer = 0;
        for (int i = 0; i < listTestNumbers.size(); i++) {
            if (checkIfMatches(baseball, listTestNumbers.get(i))) {
                answer += 1;
            }
        }
 
        return answer;
    }
 
    // nPc 구하기
    private void permutation(int[][] baseball, int depth, int n, int r) {
        if (depth == r) {
            listTestNumbers.add(toIntArray(arrNumbers, r));
            return;
        }
 
        for (int i = depth; i < n; i++) {
            swap(arrNumbers, depth, i);
            permutation(baseball, depth + 1, n, r);
            swap(arrNumbers, depth, i);
        }
    }
 
    public void swap(int[] arrNumbers, int depth, int i) {
        int temp = arrNumbers[depth];
        arrNumbers[depth] = arrNumbers[i];
        arrNumbers[i] = temp;
    }
 
    public int[] toIntArray(int[] arr, int r) {
 
        int[] result = new int[r];
 
        for (int i = 0; i < r; i++) {
            result[i] = arr[i];
        }
        return result;
    }
 
    public boolean checkIfMatches(int[][] baseball, int[] arrTestNum) {
 
        for (int i = 0; i < baseball.length; i++) {
 
            int[] arrBaseNum = new int[3];
            int iStrike = baseball[i][1];
            int iBall = baseball[i][2];
 
            arrBaseNum[0] = baseball[i][0] / 100;
            arrBaseNum[1] = baseball[i][0] / 10 % 10;
            arrBaseNum[2] = baseball[i][0] % 10;
 
            if (!checkDetail(arrBaseNum, arrTestNum, iStrike, iBall)) {
                return false;
            }
        }
        return true;
    }
 
    public boolean checkDetail(int[] arrBaseNum, int[] arrTestNum, int iStrike, int iBall) {
 
        int iTestStrike = 0;
        int iTestBall = 0;
 
        for (int i = 0; i < arrTestNum.length; i++) {
            for (int j = 0; j < arrBaseNum.length; j++) {
                // 수가 다르면 패스
                if (arrTestNum[i] != arrBaseNum[j]) {
                    continue;
                }
 
                // 자리도 같으면 Strike, 아니면 Ball
                if (i == j) {
                    iTestStrike += 1;
                } else {
                    iTestBall += 1;
                }
            }
        }
        if (iTestStrike == iStrike && iTestBall == iBall) {
            return true;
        }
        return false;
    }
}

 

너무 어려운 문제였다 ㅠㅠ

 

문제에 한번 숫자야구 게임을 해보라며 주어진 링크가 있었는데 

처음에 게임으로만 접근해서 풀었을 때는 몇 번만에 찍어서 맞췄는데,

소스로 구현할 것을 생각하며 알고리즘적으로 풀려고 하니까 한참 안풀리고 애를 먹었다.

 

그도 그럴것이, 이것은 완전탐색 문제였기 때문이다.

책(종만북)을 참고해서 적어보자면,

완전탐색(Exhaustive Search)

가능한 방법을 전부 만들어보는 알고리즘. 
얼핏 보면 이런 것을 언급할 가치가 있나 싶을 정도로 간단한 방법이지만, 
완전 탐색은 사실 컴퓨터의 장점을 가장 잘 이용하는 방법이다. 
컴퓨터는 속도가 빠르므로!

 

즉, 사람은 못하고 컴퓨터는 할수 있는 방법이라는 뜻이다 ㅋ.ㅋ

 

 

완전탐색 문제 풀이 유형은 다음과 같다. 

1. 가능한 모든 답안 후보를 먼저 구한다.

2. 후보들에 대해 답안과 일치하는지 일일이 체크한다.

 

 

위 숫자 야구 문제에서는 

각자 서로 다른 1~9까지 3자리 임의의 숫자를 정한 뒤 서로에게 3자리의 숫자를 불러서 결과를 확인합니다.

라고 했으므로, 123 ~ 987 까지의 모든 답안 후보를 먼저 만들어놓고 시작해야한다. 

 

그다음 주어진 테스트 케이스 int[][] baseball 와 일치여부를 모두 체크한다.