[프로그래머스/C++] 숫자 야구

 

완전탐색 유형에 있는 숫자 야구 문제이다.

 

완전 탐색은 이 게시판을 보면 된다.

2019/12/30 - [알고리즘/문제해결전략] - 03 알고리즘 설계 패러다임 - (6)무식하게 풀기

 

모든 경우의 수를 만들 땐 재귀함수를 이용했다.

모든 경우의 수를 만들고, base case가 되면 조건에 맞는지 확인.

 

C++을 사용.

 

1부터 9까지 카드에서 3장을 뽑아 순열을 만들도록 했다.

그리고 모든 경우의 수에서 주어진 데이터와 비교해서 일치하는 경우에 카운팅하도록 구현했다.

 

20191230

#include <string>
#include <vector>
using namespace std;
string cards="0123456789";
bool pickedCard[10]; 

bool check(string& nums, vector<vector<int>>& baseball){
    for(int i=0; i<baseball.size(); ++i){
        string instring = to_string(baseball[i][0]);
        int ss=0, bb=0;
        
        for(int j=0; j<instring.size();++j){
            int nth = nums.find(instring[j]);
            if(nth== string::npos){
                continue;
            }
            else if(nth == j){
                ss++;
            }else if(nth != j){
                bb++;
            } 
        }
        if(baseball[i][1] !=ss || baseball[i][2] != bb){
            return false;
        }
    }
    return true;
}

void sol(string &picked, vector<vector<int>>& baseball, int &ans){
    if(picked.size() == 3){
        // 체크해서 값 상승
        if (check(picked, baseball)== true){
            ans++;
        }
        return;
    }
    for(int i = 1; i<10; i++){
        //만약 이미 선택된 카드라면 패스
        if(pickedCard[i]) continue;
        
        picked.push_back(cards[i]);
        pickedCard[i] = true;
        
        sol(picked, baseball, ans);
        
        picked.pop_back();
        pickedCard[i] = false;
    }
}

int solution(vector<vector<int>> baseball) {
    int answer = 0;
    string t = "";
    sol(t, baseball, answer);
    return answer;
}