[Silver III] 숫자 야구 - 2503

문제 링크

성능 요약

메모리: 14764 KB, 시간: 112 ms

분류

브루트포스 알고리즘, 구현

제출 일자

2024년 8월 10일 00:36:04

문제 설명

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

• 영수는 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개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수, 이렇게 총 세 개의 정수가 빈칸을 사이에 두고 주어진다.

출력

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

풀이 (브루트포스 알고리즘)

생각이 필요한 문제이다. 처음 봤을 땐 나도 모르게 멍때린 문제이기도 하다...
차근차근 해야 할 것들을 정리한 후 코드를 써내려갔다.

순서

• 세 자리 숫자를 담을 boolean형 배열을 만들고, true로 모두 초기화시켜준다.
• 1~9까지의 서로 다른 수만 가능하므로, 불가능한 숫자들을 먼저 false로 바꿔준다.
  • 1~9에서 숫자가 겹치는 경우 혹은 0이 포함되는 경우를 false로 바꿔준다.
• 숫자, 스트라이크, 볼을 입력받은 후 for문으로 100~999까지 모든 숫자를 검사한다.
  • 스트라이크, 볼의 각각 카운트를 세기 위한 변수를 만든다.
  • 입력받은 수와 100~999까지의 수를 비교해, 스트라이크가 되는 경우엔 스트라이크 카운트에 + 1을 해주고, 볼이 되는 경우엔 볼 카운트에 + 1을 해준다.
• 만약 입력받았던 스트라이크와 스트라이크 카운트가 다르거나 입력받았던 볼과 볼 카운트가 다르다면 해당 수를 false로 처리한다.
• 그 후 다시 100부터 999까지 true인 수만 뽑아 answer변수에 + 1 해나간다.
• answer변수를 답으로 출력한다.

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

public class Main{
	static boolean[] number = new boolean[1000];
	static int answer=0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st;
		Arrays.fill(number, true);
		
		Initialize();
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			//각각 수 입력받음 ->숫자 / 스트라이크 / 볼
			int num = Integer.parseInt(st.nextToken());
			int strike = Integer.parseInt(st.nextToken());
			int ball = Integer.parseInt(st.nextToken());
			
			for(int j=100; j<=999; j++) { //그 숫자와 100~999까지 모든 숫자를 비교함.
				
				if(!number[j]) {
					//이미 걸러진 숫자는 필요 X
					continue;
				}
				String temp_j = Integer.toString(j); //숫자 String화
				String temp_num = Integer.toString(num); //입력받은 숫자 String화
				int countStrike = 0; int countBall = 0; //count용도
				
				for(int k=0; k<temp_num.length(); k++) {
					for(int l=0; l<temp_num.length(); l++) {
						if(k==l && temp_j.charAt(k)==temp_num.charAt(l)) { //만약 서로 자릿수가 같고, 그 자릿수의 숫자까지 같다면??
							countStrike++; //스트라이크 카운트 + 1
						}
						if(k != l && temp_j.charAt(k)== temp_num.charAt(l)) { //만약 서로 자릿수는 다르지만 숫자가 같은 수라면??
							countBall++; //볼 카운트 + 1
						}
					}
				}
				
				if(countStrike != strike || countBall != ball) { //입력 받았던 스트라이크, 볼이랑 카운트한 스트라이크, 볼이랑 다르면 false
					number[j]=false;
				}
			}
		}
		
		
		for(int i=100; i<=999; i++) {
			if(number[i]) { //true인 숫자만 체크해줌
				answer++;
			}
		}
		System.out.println(answer); 
	}
	
	public static void Initialize() { //사전 초기화 1~9까지 서로 다른 수여야 함
		for(int i=100; i<=999; i++) {
			String temp = Integer.toString(i);
			if(temp.charAt(0)== temp.charAt(1) || temp.charAt(1)==temp.charAt(2) || temp.charAt(2)==temp.charAt(0)) {
				number[i]=false;
			}
			if(temp.charAt(0)=='0' || temp.charAt(1)=='0' || temp.charAt(2)=='0') {
				number[i]=false;
			}
		}
	}
}