[백준] 2503. 숫자 야구 - 실버5

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

2503번: 숫자 야구

 

문제 요약

정답과 위치, 숫자까지 같으면 스트라이크이고, 위치는 다르지만 같은 숫자가 있으면 볼이다. 

서로 다른 세 자리 수를 원하는 만큼 입력받고, 그에 대한 스트라이크와 볼 갯수를 입력받는다.

원하는 만큼 입력받았을 때 정답이 될 수 있는 숫자의 개수를 출력한다.

 

 

문제 해결 아이디어

1부터 9까지의 숫자 중 서로 다른 3자리 수를 뽑는 것은 9P3이므로 전체 경우의 수가 크지 않기 때문에 모든 경우를 체크하는 완전 탐색 기법을 사용한다.

입력받은 세 자리 수를 100의 자리, 10의 자리, 1의 자리 순서로 배열에 넣어 주었고, 그 배열들을 또 테스트 케이스만큼 2차원 배열에 넣어 주었다.

2차원 배열의 행에 맞게 스트라이크와 볼 배열을 만들어 비교했다.

1. 1부터 9까지의 숫자 중에 3개를 뽑는 순열 배열을 만든다.
2. 3자리 수가 다 뽑아지면 그때부터 입력받은 테스트 케이스와 비교한다.
3. 뽑힌 순열 배열과 입력받은 배열을 비교해 스트라이크일 경우와 볼일 경우를 계산하고, 그 결과가 입력받은 스트라이크와 볼 배열 안의 숫자와 같다면 정답이 될 수 있는 숫자가 되는 것이다.
4. 테스트케이스를 모두 만족하는 정답이 될 수 있는 숫자가 되면, 즉 result == N일 때 출력될 카운트를 하나 증가시켜 준다.

 

 

완성 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

import javax.swing.plaf.synth.SynthSpinnerUI;

public class Main_BOJ_2503_숫자야구 {

	static int N;
	static int[] input;
	static int[] numbers; // 정답이 될 수 있는 모든 경우를 뽑기 위함
	static boolean[] isSelected;
	static int[][] question; 
	static int[] strike;
	static int[] ball;
	static int sCnt;
	static int bCnt;
	static int result;
	static int answerCnt;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		
		input = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		numbers = new int[3];

		isSelected = new boolean[input.length];

		question = new int[N][3];
		strike = new int[N];
		ball = new int[N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			char[] temp = st.nextToken().toCharArray();
			
			for (int j = 0; j < 3; j++)
				question[i][j] = temp[j] - '0';
			
			strike[i] = Integer.parseInt(st.nextToken());
			ball[i] = Integer.parseInt(st.nextToken());
		}

		// 나올 수 있는 경우의 수는 총 504개 -> 상대적으로 작음. 그냥 다 돌려보자
		// 인덱스와 숫자까지 같으면 스트라이크, 숫자는 같은데 인덱스가 다르면 볼

		sCnt = 0;
		bCnt = 0;
		result = 0;
		answerCnt = 0;
		
		permutation(0);
		
		System.out.println(answerCnt);
	} // end of main

	private static void permutation(int cnt) {
		if (cnt == 3) { // 순열 결과가 나왔을 때 -> 3자리 수가 뽑혔을 때
			
			result = 0;
			
			for (int i = 0; i < N; i++) {

				sCnt = 0; // 테스트 케이스마다 스트라이크랑 볼은 달라지니까 0으로 바꿔 주기
				bCnt = 0;

				for (int j = 0; j < 3; j++)
					if (question[i][j] == numbers[j])
						sCnt++; 

				for (int j = 0; j < 3; j++) {
					for (int k = 0; k < 3; k++) {
						if (j == k) // 인덱스마저 같으면 스트라이크니까 제외시켜 주기
							continue;
						if (question[i][j] == numbers[k])
							bCnt++;
					}
				}

				if (sCnt == strike[i] && bCnt == ball[i]) // 한개의 테스트케이스를 만족하는 경우에 result++
					result++;

			} // end of for

			if (result == N) // 테스트케이스를 모두 만족하는 경우에
				answerCnt++; // 정답이 될 수 있다
			
			return;
		}

		for (int i = 0; i < input.length; i++) {
			if (isSelected[i])
				continue;

			numbers[cnt] = input[i];
			isSelected[i] = true;

			permutation(cnt + 1);
			isSelected[i] = false;
		}
	}
}// end of class