[프로그래머스 / 완전탐색 ] 숫자 야구

1. 문제

---

코딩테스트 연습 - 숫자 야구

 

 

2. 소스코드

---

- 가능한 숫자의 모든 경우의 수는 9 x 8 x 7 = 504가지.

- 비교하는 숫자의 최대 개수는 100

- 504 x 100 = 50,400 약 5만이므로, 그냥 기본적인 완전탐색으로 충분하다. 이에 DFS로 숫자를 만들고, 3자리가 된 경우 정답여부를 확인했다.

- 숫자를 편하게 비교하고, DFS를 편하게 하기 위해서 vector<char>에 숫자를 담았다.

- 프로그래머스 완전불편함.

 

#include <string>
#include <vector>

using namespace std;
vector<char> number;
vector<vector<int>> input;
int used[10];
int ans;

void isAns() {
    bool pass = true;
    for (int i = 0; i < input.size(); ++i) {
        int strike = 0, ball = 0;
        int cmp_strike = input[i][1];
        int cmp_ball = input[i][2];
        string cmp = to_string(input[i][0]);

        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                if (number[j] == cmp[k]) {
                    if (j == k) strike++;
                    else ball++;
                    break;
                }
            }
        }

        if (!(strike == cmp_strike and ball == cmp_ball)) {
            pass = false; break;
        }
    }
    if (pass) 
        ans++;
    return;
}

void dfs(int depth) {
    if (depth == 3) {
        isAns();
        return;
    }
    for (int i = 1; i <= 9; ++i) {
        if (!used[i]) {// 사용하지 않았다면
            used[i] = true;
            number.push_back(i+'0');
            dfs(depth + 1);
            used[i] = false;
            number.pop_back();
        }
    }
}

int solution(vector<vector<int>> baseball) {
    input = baseball;
    dfs(0);

    return ans;
}