[ 백준 2503 ] 숫자 야구 (C++)

백준의 숫자야구(2503) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 입력으로 주어지는 조건에 부합하는 가능한 수의 갯수를 모두 출력하는 문제이다.

   모든 숫자에 대해서 다 해보고, 정답을 도출해내는 브루트포스 문제이다.

  

2) 먼저 우리가 알 수 있는 조건은 "숫자는 3자리 숫자이다" 라는 것과 "모든 자릿수의 숫자는 다 다르다" 를 알 수 있다.

   또한 숫자 0은 숫자에 포함되지 않는다는 것이 조건이다.

   본인은 이 문제를 해결하기 위해서, 숫자를 string형으로 표현해주었다. 왜냐하면 string형으로 표현하게 되면

   각 자리의 숫자들을 Index로 관리할 수 있고, 볼인지 스트라이크인지 관리하기가 쉽기 때문이다.

   더욱 구체적으로 알아보자.

   숫자 135 가 정답인 게임을 진행한다고 생각해보자. 우리는 숫자를 123, 235, 345 를 불렀다고 가정하겠다.

   135 , 123 = 1스트라이크 1볼

   135 , 235 = 2스트라이크

   135 , 345 = 1스트라이크 1볼   이다.

   그렇다면 위에서 말한대로 string형으로 관리하게 되면

   123에서 1 = 0번째 Index에, 2 = 1번째 Index , 3은 2번째 Index에 들어가게 된다.

   그렇다면 스트라이크는 어떻게 판단할까? 스트라이크는 우리가 말하는 숫자의 위치가 정답 숫자의 위치와 같으면 된다.

   여기서 문제가 풀만한 이유가 자릿수가 3자리 내라는 점에 주목해야 한다.

   즉, 우리가 말한 숫자를 0번 Index부터 2번 Index까지 반복시키면서, 정답숫자의 값과 Index번호까지 같다면 스트라이크,

   정답숫자의 값만 같고, Index번호가 다르다면 볼이 되는 것이다.

for(int a = 0 ; a < 3; a++)
{
    for(int b = 0 ; b < 3; b++)    
    {
        if(a == b && 말하는숫자[a] == 정답숫자[b]) 스트라이크++;
          if(a != b && 말하는숫자[a] == 정답숫자[b]) 볼++;
    }
}
 

   위와 같은 조건이 성립되는 것이다.

   위의 코드에서  a = 우리가 말하는 숫자의 Index번호, b = 정답 숫자의 Index번호를 의미한다.

   Index번호도 같고 해당 숫자의 값도 같다면 스트라이크가 ++, Index번호는 다르지만 해당 숫자가 있다면 볼++ 가 되는

   것이다.

3) 이제 위의 코드를 바탕으로 구현을 하면 되는데, 먼저 배제해야될 숫자들이 몇개 있다.

   예를 들어서 122, 130, 444 와 같은 숫자들은 우리가 탐색을 해볼 필요가 있을까? 아니다. 탐색을 해볼 필요조차 없다.

   왜냐하면 문제에서 각 자리의 숫자들은 모두 다르고, 0은 숫자에 포함되지 않는다고 했으므로, 탐색을 해볼 필요가 없다.

   즉, 문제를 시작하기전에, 123 ~ 999의 숫자들을 (100 ~ 122 도 조금만 생각해보면 당연히 안되는 숫자임을 알 수 있다)

   모두 방문해보면서, 우리가 탐색해볼만한 가치가 있는 숫자들인지에 대해서만 체크를 해주면 된다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
 
#define endl "\n"
using namespace std;
 
typedef struct
{
    int Number;
    int Strike;
    int Ball;
}Game;
 
int N;
bool Can_Number[1000];
vector<Game> V;
 
void Initialize()
{
    memset(Can_Number, true, sizeof(Can_Number));
    for (int i = 123; i <= 999; i++)
    {
        string Tmp = to_string(i);
        if (Tmp[0] == Tmp[1] || Tmp[0] == Tmp[2] || Tmp[1] == Tmp[2]) Can_Number[i] = false;
        if (Tmp[0] - '0' == 0 || Tmp[1] - '0' == 0 || Tmp[2] - '0' == 0) Can_Number[i] = false;
    }
}
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        Game G;
        G.Number = a;
        G.Strike = b;
        G.Ball = c;
 
        V.push_back(G);
    }
}
 
void Solution()
{
 
    for (int i = 0; i < V.size(); i++)
    {
        int Num = V[i].Number;
        int Strike = V[i].Strike;
        int Ball = V[i].Ball;
        string Origin = to_string(Num);
 
        for (int j = 123; j <= 999; j++)
        {
            int Tmp_Strike = 0;
            int Tmp_Ball = 0;        
 
            if (Can_Number[j] == true)
            {
                string Tmp = to_string(j);
                for (int a = 0; a < 3; a++)
                {
                    for (int b = 0; b < 3; b++)
                    {
                        if (a == b && Origin[a] == Tmp[b]) Tmp_Strike++;
                        if (a != b && Origin[a] == Tmp[b]) Tmp_Ball++;
                    }
                }
                if (Strike != Tmp_Strike || Ball != Tmp_Ball) Can_Number[j] = false;
            }
        }
    }
 
    int Answer = 0;
    for (int i = 123; i <= 999; i++)
    {
        if (Can_Number[i] == true) Answer++;
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Initialize();
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}