백준)Q.2503_숫자야구(완전탐색(Brute-fore Search))

https://www.acmicpc.net/problem/2503

2503번: 숫자 야구

문제

정보문화진흥원 정보 영재 동아리에서 동아리 활동을 하던 영수와 민혁이는 쉬는 시간을 틈타 숫자야구 게임을 하기로 했다.

• 영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324)
• 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 영수에게 묻는다. (예: 123)
• 민혁이가 말한 세 자리 수에 있는 숫자들 중 하나가 영수의 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번으로 센다. 숫자가 영수의 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼 한 번으로 센다.

예) 영수가 324를 갖고 있으면 

• 429는 1 스트라이크 1 볼이다.
• 241은 0 스트라이크 2 볼이다.
• 924는 2 스트라이크 0 볼이다.
• 영수는 민혁이가 말한 수가 몇 스트라이크 몇 볼인지를 답해준다.
• 민혁이가 영수의 세 자리 수를 정확하게 맞추어 3 스트라이크가 되면 게임이 끝난다. 아니라면 민혁이는 새로운 수를 생각해 다시 영수에게 묻는다.

현재 민혁이와 영수는 게임을 하고 있는 도중에 있다. 민혁이가 영수에게 어떤 수들을 물어보았는지, 그리고 각각의 물음에 영수가 어떤 대답을 했는지가 입력으로 주어진다. 이 입력을 바탕으로 여러분은 영수가 생각하고 있을 가능성이 있는 수가 총 몇 개인지를 알아맞혀야 한다.

아래와 같은 경우를 생각해보자.  

• 민혁: 123
• 영수: 1 스트라이크 1 볼.
• 민혁: 356
• 영수: 1 스트라이크 0 볼.
• 민혁: 327
• 영수: 2 스트라이크 0 볼.
• 민혁: 489
• 영수: 0 스트라이크 1 볼.

이때 가능한 답은 324와 328, 이렇게 두 가지이다.

영수는 동아리의 규율을 잘 따르는 착한 아이라 민혁이의 물음에 곧이곧대로 정직하게 답한다. 그러므로 영수의 답들에는 모순이 없다.

민혁이의 물음들과 각각의 물음에 대한 영수의 답이 입력으로 주어질 때 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수, 이렇게 총 세 개의 정수가 빈칸을 사이에 두고 주어진다.

 

출력

첫 줄에 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력한다.

 

예제 입력 1 

4

123 1 1

356 1 0

327 2 0

489 0 1

 

나의 풀이(코드내 설명 有)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
public class Q_2503 {
 
    static int n; // 입력받을 질문갯수
    static int countStrike; // 입력받은 Strike수
    static int countBall; // 입력받은 Ball수
    static int turn; // 질문의 차례(몇번째 질문인가)를 세기위한 변수
    static String[] numbers = new String[3]; // 입력받은 세자리 수 각 자리를 저장할 배열
    static ArrayList<Integer> list = new ArrayList(987);
    // 기준에 맞는 숫자를 저장할 ArrayList. 최대 987개의 수가 들어가므로 크기를 지정해줌.
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(br.readLine());
 
        for (int i = 0; i < n; i++) {
 
            // 입력을 받을때마다 input 배열에 넣는다.
            // input[0]은 민혁이가 질문한 세자리 숫자,
            // input[1]은 strike갯수, input[2]는 ball의 갯수가 들어간다.
            String[] input = br.readLine().split(" ");
 
            // input[0]에 있는 민혁이가 질문한 세자리 숫자를 각 자리수 대로 나눈다.
            // 123이 입력됐으면 numbers[0]에는 1, numbers[1]에는 2, numbers[2]에는 3이 들어간다.
            numbers[0] = input[0].charAt(0) + "";
            numbers[1] = input[0].charAt(1) + "";
            numbers[2] = input[0].charAt(2) + "";
 
            // 입력받은 Strike와 Ball수를 저장해준다.
            countStrike = Integer.parseInt(input[1]);
            countBall = Integer.parseInt(input[2]);
 
            // 몇번째 질문인지 세는 변수. 첫번째 질문과 이후의 질문들을 구분하기 위해 사용한다.
            turn++;
 
            // cal메서드에서 계산을 수행한다.
            cal(numbers);
        }
 
        // 반복문이 종료되고 list의 최종 size를 출력한다.
        System.out.println(list.size());
 
    } // and of main
 
    // 계산이 수행되는 cal메서드
    static void cal(String[] compare) {
 
        // 조건에 맞는 숫자를 넣을 tmp list를 선언.
        ArrayList<Integer> tmp = new ArrayList();
 
        // 123부터 987까지 반복문을 돌며 비교대상 숫자(입력된 숫자)와 strike,ball수가 일치하는지 확인한다.
        // 반복문의 역할은 123부터 987의 숫자와 입력된 숫자를 비교하고 strike갯수와 ball의 갯수를 세는 역할임.
        for (int k = 123; k <= 987; k++) {
 
            int strike = 0;
            int ball = 0;
 
            // 각 자릿수를 변수에 저장.
            int first = k / 100;
            int second = ((k - (first * 100)) / 10);
            int third = (k - (first * 100) - (second * 10));
            // 세 자리에 같은 숫자가 있거나 0이 나오면 비교하지 않고 다음 숫자로 넘어간다.
            if (first == 0 || second == 0 || third == 0 || first == second || first == third || third == second)
                continue;
            // int형 arr에 각 자릿수를 넣어준다.
            int[] arr = { first, second, third };
 
            // strike와 ball을 확인할 반복문.
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    // 비교대상 숫자와 arr[i]의 숫자가 같으면 strike아니면 ball이다
                    if (arr[i] == Integer.parseInt(compare[j])) {
                        // index까지 같으면 strike, 아니면 ball
                        if (i == j) {
                            strike++;
                            continue;
                        }
                        ball++;
                    }
                }
            }
 
            // 입력받은 countStrike와 countBall이 위의 반복문에서 계산된 strike와 ball의 수와 같으면
            // tmp ArrayList에 해당하는 숫자를 추가한다.
            if (countStrike == strike && countBall == ball) {
                tmp.add(k);
            }
        } // end of for
 
        // 반복문이 모두 끝나면 기존 list와 비교해본다.
        // turn이 1인경우에는 비교할 list가 tmp의 모든 요소들을 add한다.
        // turn이 2 이상인 경우에는 이전 turn에서 넣은 list와 tmp를 비교하여 그 둘의 교집합만 list에 남아야 한다.
        // 교집합을 구하는 메서드 retainAll사용
        if (turn != 1)
            list.retainAll(tmp);
        else
            list.addAll(tmp);
    }
 
} // end of class

알고리즘은 생각보다 간단했다. 

123~987사이의 숫자를 반복문을 돌며 '해당 숫자가 정답일 경우의 대답'과 입력된 대답(Strike,Ball)이 같은지 확인하는 것이다. 

cal메서드는 123부터 987까지 비교대상과 비교하며 반복하는 반복분이 있다. 

입력을 받자마자 cal 메서드에서 계산을 수행한다.

자세한 설명은 코드내에 있음!  

(불필요한 과정을 줄일 필요가 있어보인다..ㅜ)