[BOJ] 백준 2503 숫자 야구 / 완전 탐색(Brute-force Search)

이미지를 클릭하면 문제 사이트로 이동합니다.

---

💣 문제 이해

 

• 영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324)
• 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 영수에게 묻는다. (예: 123)
• 민혁이가 말한 세 자리 수에 있는 숫자들 중 하나가 영수의 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번으로 센다. 숫자가 영수의 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼 한 번으로 센다.
• 민혁이의 물음들과 각각의 물음에 대한 영수의 답이 입력으로 주어질 때 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력하는 프로그램을 작성하시오.

문제에 제시된 다음과 같은 조건들을 정리하면 다음과 같다.

 

1. 영수와 민혁이가 생각한 수는 세 자리 수이고, 각 자리 수는 서로 다른 숫자이다.

2. 규칙은 흔히 알고있는 숫자야구와 동일하나, 문제에서 묻는 것은 가능한 모든 숫자의 개수이다.

 

숫자의 범위도 그리 크지 않은 111 ~ 999 이고, 연산량이 많지 않아

완전 탐색(Brute-force Search) 방식을 사용하기로 했다.

 

💭 풀이 과정

 

작성 언어: C++

 

#include <iostream>
#include <string>
#include <vector>
#define NUMBERSIZE 3    // 숫자의 자리수(세자리 수이므로 3)
using namespace std;

// 입력데이터를 저장할 구조체
typedef struct inpForm{
    string number; // 숫자
    int strike; // 스트라이크 수
    int ball; // 볼 수
}INPFORM;

int arr[1000] = {0,};


int main(){
    INPFORM input; // 입력데이터를 저장할 구조체 변수
    vector<INPFORM> inpVector; // 구조체 변수를 담을 INPFORM형 벡터
    int cnt, check, result = 0;
    cin >> cnt;
    
    // 입력 데이터 벡터에 저장
    for(int i = 0; i < cnt; ++i) {
        cin >> input.number >> input.strike >> input.ball;
        inpVector.push_back(input);
    }
    
    /* 111~122, 988~999까지는 중복이 있으므로 제외
       123~987 범위에서 숫자 하나하나 체크해본다.
       질문 횟수가 4번이라면 4번을 다 확인한다.
       각 질문의 숫자를 i와 비교해서 strike, ball을 카운트하고 입력의 strike, ball과 비교한다.
       현재 숫자 i가 4번의 질문에서 모두 일치하면 정답카운트를 1 증가한다. */
    for (int i = 123; i <= 987; ++i) {
        check = 0;
        string num = to_string(i);
        // 세 자리수중에 하나라도 중복되거나 0이면 패스
        if(num[1] == '0' || num[2] == '0' || num[0] == num[1] || num[0] == num[2] || num[1] == num[2]) continue;
        
        for (int j = 0; j < cnt; ++j) {
            int stkCnt = 0, ballCnt = 0;
            
            for(int k = 0; k < NUMBERSIZE; ++k){    // 숫자의 각 세자리를 비교
                // 위치와 숫자가 일치하면 strike 카운트 증가
                if(num[k] == inpVector[j].number[k]){
                    stkCnt++;
                }
                // 위치는 다르나 숫자가 일치하면 ball 카운트 증가
                if(num[k] == inpVector[j].number[(k+1)%NUMBERSIZE] || num[k] == inpVector[j].number[(k+2)%NUMBERSIZE]){
                    ballCnt++;
                }
            }
            // strike와 ball 카운트가 입력과 동일하면 정답 카운트 증가
            if(stkCnt == inpVector[j].strike && ballCnt == inpVector[j].ball){
                check++;
            }
        }
        // i가 주어진 입력데이터를 모두 만족하는 수인 경우 결과값 증가
        if(check == cnt){
            result++;
        }
    }
    
    cout << result << endl;
    
    
    return 0;
}

 

🏆 배운 점

 

브루트 포스 방식이라고 해도 잘 감이 오지 않았다. (더 효율적인 방법을 찾아서 고민하는데 시간이 꽤나 걸림..)

이번 문제를 통해 확실히 깨달은 것은,

 

 

브루트 포스는 정말 있는 그대로 하나하나 다 확인해 보는 것이다.