swea : 숫자야구

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4su3xKXFUDFAUf

SW Expert Academy

 

나... 코테 통과할 수 있을까...?

거의 2일동안 삽질삽질끝에 겨우 해결했다!!..ㅎㅎ

 

첫번째 두번째 시도 => 이상한 방법으로 노가다....

세번째 시도 => DFS 이용해서 해결완료!

 

노가다로 푼건.. 너무 부끄러우니까 공개하지 않는걸로...

대충, ball + strike == 4 인 경우를 찾고

=> 이 경우에서 strike 개수에 따라 찾아줬다 (예에전에 숫자정렬 문제를 노가다로 풀었듯이..!)

근데.. 샘플output보다 3~4개씩 count가 많이 나왔다ㅠㅠ

 

---

일단 숫자야구에서, 특정 test에서 ball과 strike의 개수에 따라 가능성 있는 순열들이 달라지게 된다.

 

예를들어... [1234]가 ball 0, strike 1 이 나왔다고 가정했을 때,

내가 생각할 수 있는 수는..

[1???] => 근데 이제 ?에는 2, 3, 4, 가 절대 들어가지 못하는..

[?2??] => ?에는 1, 3, 4가 절대 들어가지 못함

[??3?] => ?에는 1, 2, 4가 절대 들어가지 못함

[???4] => ?에는 1, 2, 3 이 절대 들어가지 못함

이런 조건을 무조건!! 만족해야 한다는 성질이 생긴다.

=> 즉 내가 다음에 생각해낸 수열이, 위 조건을 만족하지 못한다면 query를 사용하지 않고 그냥 재낄수가 있는것이다.

 

그러면, 저런 조건을 만족한다는건 어떻게 알 수있을까? 실패한 데이터와 숫자야구를 또 해보면 된다!

예를들어, 내가 그 다음에 생각해낸 수열이 [1256]이라고 하자

=> 기존에 실패했던 수열 [1234]와 숫자야구를 하면 ball 0, strike 2라는 결과가 나온다.

=> [1234]의 query 결과와 다르면, 조건을 만족하지 못한다고 판단할 수 있다!

 

다시 내가 [1562]라는 숫자를 생각했다면...

=> [1234]와 숫자야구를 하면, ball1, strike2 라는 결과가 나온다

=> query 결과와 다르므로, 조건을 만족하지 못한것!

 

[1789] 를 생각해보면...

=> ball 0, strike 1 이라는 결과가 나온다.

=> query 결과와 같으므로, 조건을 만족했다!!

=> 이제 [1789]를 query에 넣어서 확인해보면 된다.

 

왜 query 결과와 같아야지, 조건을 만족했다고 생각하는걸까?

... 다시 생각해보면, 어떤 수열(A)의 query가 ball 1, strike 1 이었다면

적어도 해당 수열의 어떠한 숫자는 그 위치에 고정되어 있고, 어떠한 숫자는 다른위치에 존재해야만 정답에 가까워질 수 있다는걸 알 수 있다.

그럼.. 새로운 수열(B)를 생각했을 때, 위 조건을 만족한다고 하면

A와 B를 숫자야구를 했을 때 무조건 stirke 1 (어떤 숫자는 그 위치에 고정되어 있고), ball 1(어떠한 숫자는 다른위치에 존재) 라는 결과를 가지게 된다!

 

이렇게 조건을 쌓아가다보면 10번 이내에 숫자야구를 끝낼 수 있다고 한다.

만약 나중에 내가 숫자야구를 하게된다면 꼭 써먹어야 겠다 헤헤

 

#define N 4


using namespace std;

typedef struct {
           int strike;
           int ball;
} Result;
 
// API
extern Result query(int guess[]);

int data[210][6]; // {n ,n ,n ,n, b, s}
int datacount;
int visit[10];
int answer[4];

bool isok(int num[4]){
    for(int i = 0; i<datacount; i++){
        Result testresult;
        testresult.strike = 0;
        testresult.ball = 0;
        for(int j = 0; j<4; j++){
            // num[j]에 대해 테스트
            
            //strike테스트
            if(num[j] == data[i][j]){
                testresult.strike++;
                continue;
            }

            //ball 테스트
            for(int k = 0; k<4; k++){
                if(num[j] == data[i][k]){
                    testresult.ball++;
                    break;
                }
            }
        }
        if(testresult.ball != data[i][4] || testresult.strike != data[i][5]){
            return false;
        }
    }
    
    return true;
}

void coms(int index, int num[4]){
    if(index == 4){
        if(isok(num)){
            Result testresult = query(num);
            if(testresult.strike == 4){
                answer[0] = num[0];
                answer[1] = num[1];
                answer[2] = num[2];
                answer[3] = num[3];
                return;
            }
            data[datacount][0] = num[0];
            data[datacount][1] = num[1];
            data[datacount][2] = num[2];
            data[datacount][3] = num[3];
            data[datacount][4] = testresult.ball;
            data[datacount][5] = testresult.strike;
            datacount++;
        }
        return;
    }

    for(int i = 0; i<10; i++){
        if(visit[i] == 1){
            continue;
        }
        visit[i] = 1;
        num[index] = i;
        coms(index+1,num);
        visit[i] = 0;
    }

}

 
void doUserImplementation(int guess[]) {
           // Implement a user's implementation function
           //
           // The array of guess[] is a return array that
           // is your guess for what digits[] would be.

           datacount = 0;
           for(int i = 0; i<10; i++){
            visit[i] = 0;
           }

           int num[4];
            coms(0, num);

            for(int i = 0; i<4; i++){
                guess[i] = answer[i];
            }
           

}