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

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

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는 백준의 있는 다른 일반적인 문제들과 달리 '인터랙티브'로 분리되어 있는 문제이다.

   인터랙티브 문제라는 것은 쉽게 말하면 "함수만 구현" 한다고 생각하면 된다.

   즉, Main문과 구현해야 할 함수명과 그 함수의 매개변수 등과 같은 정보들이 주어지고, 구현하는 사람은

   구현하라고 주어진 함수만 구현하면 되는 문제이다.

   따라서, 별도의 입/출력을 실행할 필요도, 메인문을 구현할 필요도 없다.

   이제, 문제 풀이로 들어가보자.

   ( Main문을 포함한 기존에 주어진 정보들의 역할 등에 대해서 설명하는 부분이 있을 수 있습니다.

    따라서, 문제와 주어진 자료들을 켜놓고 읽는 것을 권장드립니다. 또한, 말이 너무 길어지다 보니 최대한

    쉽게 풀어 쓴다고 썼는데, 이해가 잘 되지 않으실 수 있으니 제일 밑에 있는 제 소스 코드를 같이 켜놓고

    읽으시는 것도 좋다고 생각합니다. )

2) 채점 프로그램과 숫자 야구 게임을 해야 한다.

   먼저, 주어진 Main문을 한번 살펴보자. 뭔지는 잘 모르겠지만, main() 함수가 하나 있고, guess() 라는 함수가

   하나 있다. guess() 함수 안의 내용을 살펴보니 매개변수로는 string 자료가 하나 전달되고,

   무슨 작업을 진행하는지는 잘 모르겠지만 가장 최종적으로 return 하는 값이, strike의 갯수와 ball의 갯수를 return 해준다.

   우리는 이것만 보고도, 대충 눈치를 챌 수가 있다. 내가 생각하는 값을 매개변수로 보내면, 이 매개변수를

   채점 프로그램이 생각하는 정답과 비교해서 strike의 갯수와 ball의 갯수를 return 해 준다는 것을 알 수가 있다.

   조금 더 깊게 들어가 보자면, 우리는 game() 함수를 구현해야 한다. 즉, 우리는 game() 함수를 구현하는 과정에서

   중간 중간 guess() 함수를 호출해서 최종 정답을 도출해 내야 하는 것이다.

   그렇다면 이제 본격적으로 game() 함수를 구현하는 과정을 한번 알아보자.

  

3) 본인은 가장 먼저, 절대로 정답의 후보 조차 될 수도 없는 값들을 걸러내 주는 과정을 진행해 주었다.

   도대체 어떤 값들이 시작하기도 전부터 정답의 후보 조차 될 수 없을까 ??

   자릿수가 3자리로 정해졌다고 가정해보면, 이런 숫자들을 생각해보자.

   121 , 122 , 555 , 977 , 080 ... 이런 숫자들을 한번 봐보자. 정답이 될 수 있는 숫자들일까 ??

   절대로 정답이 될 수 없다. 왜 ? 문제에서 0부터 9까지 서로 다른 숫자 N 개로 이루어져 있다고 말을 해줬기 때문이다.

   즉, 모든 자리의 숫자는 모두 다 달라야 한다. 즉 ! 같은 숫자가 중복되서 나올 수 없다는 말이다.

   하지만 본인이 위에서 나열한 숫자들은 ? 모두 중복되는 숫자들을 가지고 있다. 즉, 저 숫자들은 시작하기도 전부터

   정답후보 조차 될 수 없는 숫자들이다. 이러한 숫자들을 모두 걸러내 주는 작업을 가장 먼저 해 주었다.

   걸러내는 방법은 모든 숫자들을 다 탐색해 주었다. 그렇다면 3자리 숫자라고 생각했을 때, '모든 숫자'의 범위는 어떻게

   될까 ?? 아마 100 ~ 987이 될 것이다. 라고 생각하면 안된다.

   왜냐하면 '0' 이라는 숫자가 가장 앞에 오는 경우, 즉, 023 같은 경우도 가능하기 때문이다.

   그럼 범위가 어떻게 될까 ? 12 ~ 987이 될 것이다. 왜 ? 두 자릿수 앞에는 0이 있다고 생각을 하면 된다.

   012, 013, 014, 015 ~~~~ 987 까지 가면서 각 자릿수를 비교해서 같은 숫자가 2개 이상 있다면 걸러내 주었다.

   근데 범위가 왜 10 ~ 999 가 아니라 12 ~ 987 일까 ?? 10, 11은 ? 어차피 안되는 수이다. 987 < x <= 999 안에 있는

   숫자들은 ?? 직접 적어보면 알겠지만 절대 안되는 숫자들이라서 애초에 본인은 범위를 저렇게 설정해 주었다.

   그럼 '걸러낸다' 라는 것을 어떻게 구현하는지 알아보자.

   본인은 이 부분을 위해서 총 3개의 변수를 만들어 주었다.

   1. int Num_Idx[2];

   2. int Num_List[5040][2];

   3. bool Check[9877];

   위의 3가지 변수들이 의미하는 것들에 대해서 알아보자.

   먼저, 2번 변수부터 알아보겠다. Num_List 라는 것은 "후보가 될 수 있는 숫자들을 저장해 놓은 배열" 이다.

   그럼, Num_List가 2차원 배열로 선언되어 있는데, 5040과, 2의 의미를 알아보자.

   5040은 경우의 수이다. 이 문제에서 자릿수는 최대 4개까지 나올수가 있다.

   그럼, 만들 수 있는 숫자의 모든 경우의 수는 몇개가 될까 ??

   아마 10 x 9 x 8 x 7 이 될 것이다. 즉 5040 이라는 값을 얻을 수 있다. 즉, 최대 5040개의 숫자들을 저장할 수 있는

   공간을 만들어 주기 위해서 '5040' 이라는 크기로 선언해 주었다. 물론, 자릿수가 3이라면 10 x 9 x 8 로 5040보다는

   훨씬 적은 갯수의 숫자가 나오게 될 것이다. 하지만, 최대 5040개 만큼 필요하게 된다.

   뒤에 '2'는 크게 신경쓰지 않아도 된다. 이 문제에서 자릿수가 3일수도 4일수도 있기 때문에, 3일 때에는 [0]에,

   4일때는 [1]에 저장해 주었다.

   이 배열의 인덱스를 관리해주기 위해서 1번 변수인 Num_Idx라는 변수를 만들어 준 것이다.

   똑같이, [2] 는 신경쓰지 않아도 된다. 3자리일때는 [0]에, 4자리일때는 [1]에 저장해 준 것 뿐이다.

   예를 한번 들어보자.

   3자리 숫자일 때, 우리는 12 ~ 987 까지 반복하면서 중복된 숫자가 없다면 이 값을 Num_List에 넣어주는 작업을

   진행할 것이다. 첫번째로 '012'는 중복된 숫자가 없으므로 Num_List에 들어가게 될 것이다.

   즉, Num_List[0][0] = 12 가 될 것이다.  Num_List[1][0] = 13, Num_List[2][0] = 14... 이런식으로 저장될 것이다.

   뭔가 1번 변수도 배열로 선언되어 있고, 2번 배열도 2차원 배열로 선언되어 있어서 헷갈려 보일 수 있는데

   자릿수가 3자리 일수도 4자리 일수도 있기 때문에 이를 구분하기 위해서 붙여준 놈들일 뿐이니 어렵게 생각하지 말자.

   만약, 자릿수가 하나의 자릿수로 고정되어 있었다면 1번 변수는 Num_Idx, 2번 변수는 Num_List[5040] 이였을 것이다.

   이제 3번 변수를 알아보자. Check[a] = true 의 의미는 "a라는 숫자는 아직 정답일 가능성이 있는 숫자입니다." 를

   의미한다. 그럼 크기가 왜 9877 일까 ?? 4자리일 경우 숫자의 범위는 123 ~ 9876 이 된다. 즉, 가장 큰 '9876' 이라는

   숫자까지 저장할 수 있어야 하기 때문에 크기를 9877로 잡아주었다.

   그럼 초기 상태는 어떻게 될까 ?? 지금 까지 한 걸 정리하면서 생각해보자.

   1. 시작 전에, 중복된 숫자가 존재하는 숫자들은 걸러내 주었다.

   2. 과정 1에 의해서 걸러내어 지지 않은, 즉 살아남은 숫자들을 Num_List에 저장해 주었다.

   즉, Check배열의 초기상태는, 걸러지지 않은, 즉 Num_List에 저장된 숫자들을 모두 true로 설정해 주어야 한다.

   왜 ? 아직 야구 게임을 시작도 안했는데, 살아남은 모든 숫자들은 정답일 가능성이 있는 숫자들 이니까 !

   여기서 하나만 짚고 넘어가자 ! 이 문제에서는 여러개의 Test Case를 한번에 실행하게 된다. 또한 그 여러개의

   Test_Case들은 모두 자릿수가 동일하다. 그렇다면, 우리가 위에서 했던, "시작전부터 정답이 될 수 없는 숫자들을

   걸러내는 과정" 을 매 Test_Case마다 진행해줘야 할까 ?? 아니다. 그럴 필요가 없다. 시간만 낭비할 뿐이다.

   첫 번째 테스트 케이스에서 '121' 이라는 숫자를 걸러냈는데, 두 번째 테스트 케이스에서 '121'이 갑자기 정답이 될 수

   있는 가능성을 가진 숫자가 되거나 하진 않는다. 즉, 걸러내는 과정은 가장 처음에 한번만 할 수 있도록 설정해주자.

   그럼 Check배열은 ?? 여기까지만 읽었을 때는 잘 모르겠지만, 본격적인 야구 게임이 시작되면 정답이 될 수 없는

   숫자들을 Check배열에서 false로 바꿔주면서 게임을 진행한다. 즉, Check배열은 매 Test_Case마다 초기화를 해 주어야

   한다 !

   아직 야구게임 시작하지도 않았는데 너무 길이 글어진 것 같다. 깔끔하게 정리한번 해보고 가자.

   1. 처음부터 답이 될 수 없는, 즉 중복된 숫자가 존재하는 숫자들을 걸러내 주었다.

   2. 살아남은 숫자들을 Num_List 라는 배열에 저장해 주었다. 3자리일 경우에는 Num_List[][0]에,

     4자리일 경우에는 Num_List[0][1]에 저장해 주었다. 그리고, 3자리 일 경우 살아남은 숫자의 총 갯수는 

     Num_Idx[0]에, 4자리 일 경우 Num_Idx[1]에 저장되어 있을 것이다.

   3. 또한, Num_List 배열에 저장된 숫자들을 Check[] 배열에 true로 표시해 줌으로써, 정답일 가능성이 있다고

     판단할 수 있게 만들어 주었다.

4) 이제 정말로 게임을 시작해보자. 본인은 가장 직관적으로 "현재 정답일 가능성이 있는 숫자들 중, 가장 처음 나오는

   숫자"를 guess() 의 매개변수로 호출해 보았다. 호출하게 되면, 해당 숫자의 strike 갯수와 ball 갯수를 알게 될 것이다.

   그럼 지금부터 이 strike와 ball의 갯수로 알 수 있는 것들에 대해서 한번 생각을 해보자.

   예를 들어서, 채점 프로그램이 생각하는 숫자, 즉 정답이 "1432" 일 때, 내가 "1234"를 호출했다고 생각해보자.

   그럼 아마 2strike, 2ball 이 return 될 것이다. 그럼 우리는 이 2strike 2ball로 알아낼 수 있는게 있을까 ??

   가장 쉽게 한번 생각해보자. "9876"을 우리는 호출을 해보진 않았지만, 9876이 정답일 수 있을까 ?? 정답이 아니라는 것을,

   더 나아가서는 정답의 가능성 조차 없는 숫자라는 것을 알 수 있다.

   그럼, 쪼금 더 어려운 숫자로 생각해보자. "3124" 이라는 숫자는 ?? 정답의 가능성이 있는 놈일까 없는놈일까 ??

   없는 놈이라는 것을 생각을 조금만 한다면 알 수 있다. 왜 ?? "1234"가 2strike 2 ball이였다.

   저 말을 쉽게 한국말로 써보자면 "1234 라는 숫자는, 정답의 숫자랑 비교했을 때, 숫자와 위치가 일치하는 숫자가 2개

   이고 숫자는 일치하지만 위치가 일치하지 않는 숫자가 2개입니다." 라는 말이다.

   그럼 최소한 정답이 되기 위해서는, "1234"라는 숫자와 비교해 봤을 때, strike 갯수와 ball의 갯수가 맞아야 정답의 후보가

   될 수 있지 않을까 ?? "1234"와, "3124"를 비교하면 1strike, 3ball 이다. 이 말을 한국말로 써보자면

   "3124는 1234와 비교를 해봤을 때, 숫자와 위치가 일치하는 숫자가 1개이고, 숫자만 일치하는 숫자가 3개입니다" 라는

   것이다. "1234"가 정답과 비교했을 때, 숫자와 위치가 일치하는 숫자가 2개, 숫자만 일치하는 숫자가 2개였는데,

   3124는 그런 1234와 비교를 했을 때 숫자와 위치가 일치하는 숫자가 1개밖에 되지 않는다. 과연 정답이 될 수 있을까 ??

   정답이 될 수 없는 숫자라는 것이다.

   그럼, "1243"은 ?? "1234"와 비교해 봤을 때, 2strike, 2ball의 결과를 가져오게 된다. 즉, 정답이 될 가능성이 없지는

   않은 놈이라는 것이다.

   정리를 해보자면 "guess() 함수를 통해서 얻은 결과로, 우리는 정답의 가능성이 없는 숫자들을, guess() 함수 호출

   없이도 파악할 수 있다 라는 것이다. 어떻게 ? guess()함수를 호출한 숫자와, 남은 숫자들을 비교해서, guess()

   함수의 결과와 일치하지 않는다면, 그 숫자는 정답의 가능성이 없는 숫자가 되버린다."

   너무 헷갈린다면 "3124, 1234" 같은 숫자들 말고, 가장 쉬운 숫자인, "1234"를 통해서 2strike, 2ball을 얻었다고 가정했을 때,

   너무나도 당연하게 "9876"을 정답의 후보에서 제외하는 이유에 대해서, 당연하게 생각하지 말고 한번 생각을 해보자 !

   본인은 이런 방식으로 계속 반복해 준다. 뭐를 반복하는지 다시 한번 정리해보자.

   1. 정답의 후보가 될 수 있는 숫자들 중, 가장 빠른 숫자를 guess() 함수로 호출한다.

   2. guess() 함수의 결과를 통해서, 남은 숫자들 중에서 정답이 될 수 없는 숫자들을 걸러준다.

   이 2가지를 반복하는 것이다. 이게 본인이 구현한 game() 함수의 내용들이다.

   그런데, 이거를 한번만 딱 하고 끝내는 것이 아니다. 무한루프 안에서, 정답이 나올 때 까지 반복해 주어야 한다.

  

   이대로 끝나면 참 좋겠지만, 우리가 구현해야 할 함수는 Init() 함수가 하나 더 있다.

   Init() 함수에서 할 내용은 이미 우리가 다 알고 있는 내용들 뿐이다.

   본인이 Init() 함수에서 구현한 것은 딱 2가지이다.

   처음에 시작도 전에 걸러낸 숫자들(중복된 숫자가 존재하는 숫자들)을 걸러내는 과정, 또 하나는 자릿수를 나만의

   전역변수에 설정해주는 과정 2가지 뿐이다.

   글이 너무 길었다 보니 마지막으로 최종정리 한번 하고 소스코드 보도록 하자.

   1. 시작하기 전부터, 우리는 정답이 될 수 없는 숫자들을 알고있다. 바로 중복된 숫자가 존재하는 숫자들이다.

      이 숫자들을 먼저 걸러내자. - Init() 함수

   2. 1의 과정에서 살아남은 숫자들, 즉, 정답의 후보를 무한히 지니고 있는 숫자들을 Check[] 라는 배열을 통해서

     관리하기 위해서 Check[]배열에 표시해주자.

   3. 살아남은 숫자들 중에서, 가장 빠른 숫자를 guess() 함수에 호출하자.

   4. guess() 함수의 결과를 통해서, 정답이 될 수 없는 숫자들을 걸러내 주자.

   5. 3 ~ 4의 과정을 반복해주자. 언제까지 ? guess() 함수의 return 값 중, strike 값이 자릿수 일 때 까지 !

   ( 소스 코드에도 주석을 최대한 달아놓았으니 참고하세요 ! )

[ 소스코드 ]

#include "NB.h"
#include<string>
using namespace std;
 
#define NUM_MAX 9877
#define LIST_MAX 5040
 
struct STATE
{
    int Strike;
    int Ball;
};
 
int My_N;
int Num_Idx[2];
int Num_List[LIST_MAX][2];
bool Check[NUM_MAX];
/* 전역변수 설명 */
/* My_N = 자릿수(N)의 값을 나만의 전역변수에 저장하고 관리하기 위한 변수.
 * Num_Idx[] = 각 자릿수에서, 정답이 될 수 있는 후보들의 갯수를 저장하고 있는 변수.
               [0]에는 3자리 숫자일때, [1]에는 4자리 숫자일 때의 갯수가 저장된다.
               또한, Num_List의 Idx를 관리하기 위해서 사용되는 변수이다.
 * Num_List[][] = 실제 살아남은 숫자들이 저장되는 배열이다. 최대 5040개의 숫자를 가질 수 있다.
 * Check[] = 정답의 후보인 숫자들을 관리하기 위해서 만든 변수이다.
 */
 
void Make_Number_List()
{
    /* 가장 초기 상태 설정 과정 */
    /* 3자리이든, 4자리이든, 모든 숫자들을 탐색하면서, 중복된 숫자를 가진 숫자라면
       걸러내 주는 작업을 해주는 함수.
     * 또한, 살아남은 숫자들을 Num_List에 저장해 주는 역할을 수행하는 함수이다.
     * 이 과정은, 가장 처음 딱 1번만 해주면 된다.
     */
    if (My_N == 3)
    {
        for (int i = 12; i <= 987; i++)
        {
            int First = i / 100;
            int Second = i % 100 / 10;
            if (First == Second) continue;
 
            int Third = i % 10;
            if (First == Third || Second == Third) continue;
 
            Num_List[Num_Idx[0]++][0] = i;
        }
    }
 
    if (My_N == 4)
    {
        for (int i = 123; i <= 9876; i++)
        {
            int First = i / 1000;
            int Second = i % 1000 / 100;
            if (First == Second) continue;
 
            int Third = i % 100 / 10;
            if (First == Third || Second == Third) continue;
 
            int Fourth = i % 10;
            if (First == Fourth || Second == Fourth || Third == Fourth) continue;
 
            Num_List[Num_Idx[1]++][1] = i;
        }
    }
}
 
void init(int T, int N)
{
    /* Init() 함수. */
    My_N = N;
    Make_Number_List();
}
 
STATE Compare(int A, int B)
{
    /* 2개의 숫자를 비교하는 함수. */
    /* guess() 함수를 통해서 얻은 결과와, 그 결과를 통해서 걸러낼 수 있는 숫자들을 
       파악하는 함수이다.
     * Strike의 갯수와 ball의 갯수가, guess() 함수의 결과값과 다르다면 그 숫자는
       해보지도 않고, 정답이 될 수 없는 숫자로 판단하기 위해서 strike, ball의 갯수를 파악하는 함수.
     * ex) '1234'를 통해서 '9876'이 정답이 아니라는 것을 판단.
     */
 
    STATE R = { 0 , 0 };
    int Arr[10];
    for (int i = 0; i < 10; i++) Arr[i] = 0;
 
    /* 자릿수 만큼 돌면서, Strike와 ball의 갯수 파악. */
    for (int i = 0; i < My_N; i++)
    {
        if (A % 10 == B % 10) R.Strike++;
        else
        {
            Arr[A % 10]++;
            Arr[B % 10]++;
        }
 
        /* 특정 숫자의 갯수가 2개가 되었다 = ball을 의미. */
        /* 1234 와 1432 를 비교 한다면, 
           가장 마지막 자리부터 비교를 시작.
           1. '4'와 '2'에서 4의 갯수++, 2의 갯수++
           2. '3'과 '3'에서 Strike++
           3. '2'와 '4'에서 2의 갯수++, 4의 갯수++
              - 여기서 2와 4의 갯수가 2개가 되었네 ? = ball 을 의미.
           4. '1'과 '1'에서 Strike++
         */
        if (Arr[A % 10] == 2) R.Ball++;
        if (Arr[B % 10] == 2) R.Ball++;
 
        A = A / 10;
        B = B / 10;
    }
    return R;
}
 
void game() 
{
    /* 실제 야구 게임을 하는 과정 */
    /* 가장 먼저, Check배열 초기화 !! */
    for (int i = 0; i < Num_Idx[My_N - 3]; i++)
    {
        Check[Num_List[i][My_N - 3]] = true;
    }
 
    while (1)
    {
        int Candidate_Num;
        string S = "";
 
        /* 정답이 될 수 있는 후보들 중에서, 가장 먼저 나온 값을 guess() 함수에 호출 하기.*/
        /* guess() 함수의 매개변수가 string형이라서, int를 string으로 변환해주어야 한다. */
        if (My_N == 3)
        {
            for (int i = 0; i < Num_Idx[My_N - 3]; i++)
            {
                if (Check[Num_List[i][My_N - 3]] == true)
                {
                    Candidate_Num = Num_List[i][My_N - 3];
                    int First = Candidate_Num / 100;
                    int Second = Candidate_Num % 100 / 10;
                    int Third = Candidate_Num % 10;
                    S = S + (char)((First + '0'));
                    S = S + (char)((Second + '0'));
                    S = S + (char)((Third + '0'));
                    break;
                }
            }
        }
        else
        {
            for (int i = 0; i < Num_Idx[My_N - 3]; i++)
            {
                if (Check[Num_List[i][My_N - 3]] == true)
                {
                    Candidate_Num = Num_List[i][My_N - 3];
                    int First = Candidate_Num / 1000;
                    int Second = Candidate_Num % 1000 / 100;
                    int Third = Candidate_Num % 100 / 10;
                    int Fourth = Candidate_Num % 10;
                    S = S + (char)((First + '0'));
                    S = S + (char)((Second + '0'));
                    S = S + (char)((Third + '0'));
                    S = S + (char)((Fourth + '0'));
                    break;
                }
            }
        }
 
        /* String으로 변환한 해당 값을 guess()로 호출. */
        /* guess()의 return 값 중, strike = 자릿수 이면, 게임 끝. */
        /* 그게 아니라면, 그 숫자는 일단 정답이 될 수 없는 숫자이므로 Check. */
 
        pair<int, int> Res = guess(S);
        if (Res.first == My_N) break;
        else Check[Candidate_Num] = false;
 
        /* 하지만, 그 숫자를 통해서 정답이 아닌 다른 숫자들을 찾아내는 과정. */
        /* guess() 함수를 호출했던 숫자와, 다른 숫자들을 비교해서, { strike, ball } 의 갯수 비교. */
        /* 비교 후, 걸러낼 수 있는 숫자 걸러내주기. */
        for (int i = 0; i < Num_Idx[My_N - 3]; i++)
        {
            if (Check[Num_List[i][My_N - 3]] == true)
            {
                STATE Cmp = Compare(Candidate_Num, Num_List[i][My_N - 3]);
                if (Res.first != Cmp.Strike || Res.second != Cmp.Ball) Check[Num_List[i][My_N - 3]] = false;
            }
        }
    }
}