[c++] 프로그래머스 :: 숫자야구 (brute force)

 

숫자야구

코드

#include <string>
#include <vector>

using namespace std;

bool check(int* arr, vector<int>& bb) {
    int num = bb[0]; int s = bb[1]; int b = bb[2];
    int n[3]; n[0] = num / 100; n[1] = (num - n[0] * 100) / 10; n[2] = (num - n[0] * 100 - n[1] * 10);
    //strike check
    int t_num = 0;
    for (int i = 0; i < 3; i++) {
        if (n[i] == arr[i])
            t_num++;
    }
    if (t_num != s)
        return false;
    t_num = 0;
    for (int i = 0; i < 3; i++) {
        if (n[i] == arr[(i + 1) % 3] || n[i] == arr[(i + 2) % 3])
            t_num++;
    }
    if (t_num != b)
        return false;
    return true;
}

int solution(vector<vector<int>> baseball) {
    int answer = 0;
    int size = baseball.size();

    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            if (j == i)
                continue;
            for (int k = 1; k <= 9; k++) {
                if (k == i || k == j)
                    continue;
                int flag = 1;
                int arr[3] = { i,j,k };
                for (int l = 0; l < size; l++) {
                    if (!check(arr, baseball[l])) {
                        flag = 0;
                        break;
                    }
                }
                if (flag)
                    answer++;
            }
        }
    }
    return answer;
}

알고리즘 설명

1. 세 자리 수를 1~9까지 서로 다른 수로 완전 탐색하면서 check 할 수를 구한다.
2. check 할 수를 이미 주어진 baseball vector에 맞는지 check 한다.
   1. strike 횟수는 같은 위치에 같은 요소가 있는지 확인한다.
   2. ball 횟수는 다른 위치에 같은 요소가 있는지 확인한다.

시간 복잡도

숫자가 3자리 수이고 각 자리마다 1~9까지 돌면서 만들어지기 때문에 check해야할 수는 9*8*7 =504 개이다. 한 수마다 baseball vector 갯수만큼 check를 하는데, check 함수의 시간복잡도가 상수이므로 baseball vector의 갯수를 n으로 하면 n만큼의 시간이 걸린다.

따라서 각 숫자마다 n만큼의 시간이 걸리므로 504개의 수를 check하는데에는 504n 만큼의 시간이 걸린다.

함정

처음에 brute force 문제인지 까먹고 조건으로 풀었는데 굉장히 코드가 복잡했다. strike, ball 의 조건이 해당 위치에 그 요소가 존재한다는 정보만을 포함하는 것이 아니라 다른 위치에 그 요소가 존재한다는 정보도 포함해야하므로 고려해야할 사항이 너무 많다.

ex_) 123 1 1 이면

strike가 1이니까 1xx , x2x, xx3 이 후보가 될 수 있지만, 이뿐만 아니라 남은 두 자리에 해당 수가 들어가지 않는다는 정보도 포함해야한다. 따라서 brute force가 이를 간단하게 만들어 줄 수 있다.