[SW Expert Academy] 1768. 숫자야구게임

Posted on July 07, 2021

문제 :

Main 부분으로 제공되는 main.cpp 또는 Solution.java 코드는 숫자 야구 게임을 시뮬레이션 하는 코드이다. 숫자 야구 게임은 2명이 하는 게임으로 다음과 같이 진행된다. 게임 참여자들을 Player 1과 Player 2로 나타낸다.

① Player 1은 중복되지 않는 숫자들로 구성된 4 자리의 수를 생각한다. (이 수를 생각하는 수라 하자. 생각하는 수는 0부터 시작할 수 있다.) ② Player 2는 중복되지 않는 숫자들로 구성된 4 자리의 수를 추측해서 물어본다. (이 수를 물어보는 수라 하자. 물어보는 수 또한 0부터 시작할 수 있다.) ③ Player 1은 생각하는 수와 물어보는 수를 비교해서 스트라이크와 볼의 개수를 알려준다. ④ 스트라이크의 개수는 생각하는 수와 물어보는 수가 같은 숫자를 가지고 있고 자리 위치까지 맞은 숫자의 개수이다. ⑤ 볼의 개수는 생각하는 수와 물어보는 수가 같은 숫자를 가지고 있지만 자리 위치는 서로 다른 숫자의 개수이다. ⑥ 만약 생각하는 수와 물어보는 수가 일치하면 게임이 끝난다. ⑦ 만약 생각하는 수와 물어보는 수가 일치하지 않으면 ②번으로 돌아가 과정들을 반복한다.

가령 예로, Player 1은 ‘1234’를 생각하고 있다고 하자.

Player 2가 ‘4139’으로 물어보면 Player 1은 1 스트라이크 2 볼이라 알려준다. ‘1234’와 ‘4139’를 비교하면 두 수 모두 가지고 있는 숫자들은 ‘1’과 ‘3’과 ‘4’이고 그 중에 자리 위치까지 맞은 숫자는 ‘3’이다. ‘1’과 ‘4’는 자리 위치가 서로 다르다.

Player 2가 ‘2567’으로 물어보면 Player 1은 0 스트라이크 1 볼이라 알려준다. ‘1234’와 ‘2567’을 비교하면 두 수 모두 가지고 있는 숫자는 ‘2’이고 자리 위치는 서로 다르다.

Player 2가 ‘0768’으로 물어보면 Player 1은 0 스트라이크 0 볼이라 알려준다. ‘1234’와 ‘0768’을 비교하면 두 수 모두 가지고 있는 숫자는 없다.

시뮬레이션에서는 Player 1이 컴퓨터가 되고 생각하는 수는 각 테스트 케이스로 주어진다.

query 함수를 이용하여 생각하는 수를 맞추도록 Player 2에 해당하는 doUserImplementation 함수 또는 UserSolution.doUserImplementation 메소드를 구현하라.

만약 query 함수를 호출할 때 중복된 숫자가 있으면, 잘못된 질문으로 간주하고 스트라이크와 볼이 각각 –1 값이 저장되어 리턴된다.

더 자세한 내용은 주어진 소스코드를 참조하라.

[제약 사항]

생각하는 수는 4 자리의 수이다.
생각하는 수는 0부터 9까지 중복되지 않는 숫자로 이루어진다.
생각하는 수는 0부터 시작할 수 있다.
각 테스트 케이스에서 query 함수의 호출한 횟수가 일정 수준 이하이고 생각하는 수와 guess 배열에 저장된 값이 일치하는 경우만 점수를 얻는다.
동점자인 경우 query 함수를 호출한 총 횟수가 적을 수록 유리하다.(Java인 경우 Solution.query 메소드를 호출한 총 횟수이다.)

입력 :

입력 첫 줄에는 총 테스트 케이스 개수 T(1 ≤ T ≤ 50)가 주어진다.

그 다음 줄부터 테스트 케이스 T개가 온다. 각 테스트 케이스는 모두 1 줄로 구성되어 있다.

각 테스트 케이스의 첫 번째 줄에는 생각하는 수가 주어진다.

풀이 :

=> 우선 삼성 역량 테스트 “B”형을 준비하기 위해 샘플 문제를 풀어보았다.

기존 알고리즘 테스트 문제들과 유형부터 구현 방식까지 다른 점이 많아서 준비를 많이 해야겠다는 생각이 가장 많이 든 것 같다.

우선 아직 더 풀어봐야 알겠지만 나름 나만의 전략(?)을 세워보았다.

[ 오스타 B형 공략법 ]

라이브러리 사용불가 - 아직 테스트를 쳐보진 않았지만 레퍼런스 코드가 주어진다고 한다. 하지만 레퍼런스 코드가 완전히 최적화된 알고리즘, 자료 구조 코드가 아니기 때문에 적어도 각 자료구조, 알고리즘 코드들을 내가 직접 구현할 수 있고 레퍼런스 코드 이해가 확실하게 이뤄져야 할 것 같다
제공 코드 이해가 첫 단계! - B형의 경우 보통 Main 코드가 주어지고 Solution 코드를 API 형식으로 작성해서 문제를 해결하는 방식이다. 따라서 Main의 구현되어있는 변경 불가능한 함수들의 용도와 로직을 확실하게 이해한 후부터 코드를 설계해나가도록 하자.
최적화가 포인트 ! - 기존의 알고리즘 문제들처럼 해결했다고 넘어가는 방식보다는 많은 실력자분들의 코드를 리뷰해보고 최적화할 수 있는 방법들을 참고하는 방식으로 공부해야 효과적일 듯 하다.

본 문제는 우선 doUserImplementation(int guess[]) 함수가 최대한 적은 query(제안 숫자가 생각하는 숫자와 얼마나 유사한지 스트라이크, 볼 카운트를 반환해줌) 함수 호출로 생각하는 숫자를 알아내는 기능을 구현해야 한다.

구현 방식은 다음과 같다.

0123 ~ 9876 사이에 각 자릿수가 중복되지 않는 숫자들 중에서 생각하는 숫자가 존재한다. 따라서 query() 함수에 판단해볼 만한 숫자들만 유효하다고 true 표시를 해줄 validary[9877] 배열을 준비한다.
validary 배열에 우선 각 자릿수가 다른 수들만 true 표시를 하도록 초기화한다.
이후에 0123부터 반복문을 돌리며 유효한 숫자로 표시된 숫자들만 query()함수로 생각하는 숫자와 동일한지 판단한다.
이 과정에서 query() 함수를 호출할 경우 현재 제안 숫자와 생각하는 숫자 사이의 스트라이크, 볼 카운트를 반환받을 수 있다. 이 반환된 스트라이크, 볼 카운트를 통해 다시 제안숫자와 해당 카운트 조건이 부합되지 않는 숫자들은 validary에서 false 표시를 해준다.
이런 과정을 반복시 최소의 query()함수 호출로 생각하는 숫자를 알아낼 수 있다.
본 문제는 시간복잡도가 아닌 query() 함수 호출의 최소화를 목표로 하는 문제였기에 생소한 문제였던 것 같다. 여러 문제를 풀어볼 필요가 있을 것 같다.

코드 :

코드 보기/접기

//Solution.cpp

#define N 4
#define MAX 9877

typedef struct {
    int strike;
    int ball;
} Result;

Result result;
bool validary[MAX];
int dvdary[4] = {1, 10, 100, 1000}, guesscnt[10];

// API
extern Result query(int guess[]);

bool ballCountCheck(int num, int comp) {
    int strikecnt = 0, ballcnt = 0;

    for (int k = 3; k >= 0; k--) {
        int orgnum = num / dvdary[k], compnum = comp / dvdary[k];
        if (orgnum == compnum) strikecnt++;
        else if (guesscnt[compnum]) ballcnt++;
        num %= dvdary[k];
        comp %= dvdary[k];
    }

    if (result.strike == strikecnt && result.ball == ballcnt) return true;
    return false;
}

bool guessValidCheck(int num) {
    int cntary[10]{0};
    for (int k = 3; k >= 0; k--) {
        int digit = num / dvdary[k];
        if (cntary[digit]++) return false;
        num %= dvdary[k];
    }
    return true;
}

void doUserImplementation(int guess[]) {
    int start = 123, end = 9876;

    for (int i = start; i <= end; i++)
        if (guessValidCheck(i)) validary[i] = true;

    for (int i = start; i <= end; i++) {
        if (!validary[i]) continue;

        int curnum = i;
        for (int j = 0; j < 10; j++)
            guesscnt[j] = 0;

        for (int j = 3; j >= 0; j--) {
            int digit = curnum / dvdary[j];
            guess[3 - j] = digit;
            guesscnt[digit]++;
            curnum %= dvdary[j];
        }

        result = query(guess);
        if (result.strike == 4) return;

        for (int j = i; j <= end; j++) {
            if (!validary[j]) continue;
            if (!ballCountCheck(i, j)) validary[j] = false;
        }
    }
}

Algorithm

algorithm SW Expert C++