[백준] 알고리즘 분류(브루트 포스,JAVA)2503번, 숫자 야구

문제 링크

2503번: 숫자 야구

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 정답은 서로 다른 3개의 1~9의 숫자로 주어집니다.

2. 수의 위치와 숫자가 같으면 스트라이크, 위치는 다르지만 정답에 숫자가 존재하면 볼입니다.

3. N개의 질문에 응답이 있을 때 정답 가능성이 있는 답의 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 숫자 야구에 나올 수 있는 숫자의 모든 경우와 응답에 내용과 비교합니다.

 

3. 모든 응답에 만족하는 숫자의 개수를 결과로 출력합니다.

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 4

Num	S	B
123	1	1
356	1	0
327	2	0
489	0	1

 

 

2. 숫자 야구에 나올 수 있는 숫자의 모든 경우와 응답에 내용과 비교합니다.

※응답에 만족하는 2개의 경우와 아닌 경우 1개 대해서 진행되는 과정을 보여드리겠습니다.

 

숫자 야구에서 나올 수 있는 숫자 : 123, 124, 125, ..... , 987

 

나올 수 있는 숫자 : 324일 때

 

나올 수 있는 숫자	물어본 숫자	S	B	만족여부
324	123	1	1	O
324	356	1	0	O
324	327	2	0	O
324	489	0	1	O

모든 응답과 동일하게 만족함으로써 정답이 될 수 있는 가능성이 있습니다.

 

나올 수 있는 숫자 : 328일 때

나올 수 있는 숫자	물어본 숫자	S	B	만족여부
328	123	1	1	O
328	356	1	0	O
328	327	2	0	O
328	489	0	1	O

모든 응답과 동일하게 만족함으로써 정답이 될 수 있는 가능성이 있습니다.

 

나올 수 있는 숫자 : 513일 때

나올 수 있는 숫자	물어본 숫자	S	B	만족여부
513	123	1	1	O
513	356	0	2	X
513	327	0	1	X
513	489	0	0	X

모든 응답과 동일하게 만족하지 않음으로써 정답이 될 수 없습니다.

 

3. 모든 응답에 만족하는 숫자의 개수를 결과로 출력합니다.

 

2(324, 328)을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 응답에 대한 정보를 띄어쓰기 기준 나누었습니다.
• search함수를 이용하여 숫자야구에 모든 숫자의 경우를 구한 뒤 응답이 만족하는지 확인하였습니다.
• 모든 응답에 만족하는 숫자의 개수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 재귀를 통해서 숫자야구가 가능한 모든 숫자를 탐색한 뒤 numCheck를 실행합니다.
• numCheck함수는 모든 응답에 만족하는지 확인하는 함수입니다.

 

import java.io.*;
import java.util.*;


public class Main {
    //숫자 야구 응답 정보 관련 클래스
    static class info{
        int strike, ball;
        String num;
        public info(String num, int strike, int ball){
            this.num = num;
            this.strike = strike;
            this.ball = ball;
        }
    }
    static int N;
    static ArrayList<info> game = new ArrayList<>();	//숫자 야구 응답 저장 리스트
    static ArrayList<String> answer = new ArrayList<>();	//정답 가능한 숫자 저장 리스트
    static boolean[] numUsing;		//숫자 사용 여부 확인 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        numUsing = new boolean[10];
        StringTokenizer st;
        //응답 관련 정보 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            String num = st.nextToken();
            int s = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            game.add(new info(num, s, b));
        }
        search("", 0);	//숫자야구 모든 경우의 수 탐색
        bw.write(answer.size() + "");	//정답이 가능한 숫자개수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //숫자야구의 모든 경우 만드는 함수
    static void search(String num, int size){
        //완성된 경우 모든 응답 만족하는지 확인하기.
        if(size == 3){
            numCheck(num);
            return;
        }
        //숫자야구에 나올 수 있는 숫자 만들기.
        for(int i=1;i<=9;i++){
            if(!numUsing[i]){
                numUsing[i] = true;
                search(num + i, size + 1);
                numUsing[i] = false;
            }
        }
    }
    //숫자가 모든 응답에 만족하는지 확인하는 함수
    static void numCheck(String num){
        //모든 응답에 대하여 만족하는지 탐색
        for(info cur : game){
            int s = 0;
            int b = 0;
            //스트라이크 조건 만족하는지 확인
            for(int i=0;i<3;i++)
                if(cur.num.charAt(i) == num.charAt(i))
                    s++;

            if(cur.strike != s)
                return;
            //볼 조건 만족하는지 확인
            for(int i=0;i<3;i++){
                int temp = (i + 1) % 3;
                if(num.charAt(i) == cur.num.charAt(temp))
                    b++;
                temp = (i + 2) % 3;
                if(num.charAt(i) == cur.num.charAt(temp))
                    b++;
            }

            if(cur.ball != b)
                return;
        }
        //모든 조건 만족할 때 추가
        answer.add(num);
    }
}