[백준] 2503번: 숫자 야구

문제

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

영수와 민혁이가 숫자야구 게임을 한다고 한다.
영수가 1~9까지 서로 다른 숫자 3개로 구성된 세자리 수를 생각한다.
민혁이가 이를 물어본다. 대답으로 돌아오는 것은 두가지
1. 민혁이가 말한 숫자에서 영수가 생각한 숫자의 자릿수와 일치하게 존재하면 스트라이크
2. 민혁이가 말한 숫자에서 영수가 생각한 숫자에 존재하지만 자릿수가 다르면 볼

예를 들어서 영수가 324를 생각했다고 하자

• 민혁이가 429를 물어봤다면 1 스트라이크 (2) 1볼(4)이다.
• 민혁이가 241을 물어봤다면 0 스트라이크 2볼(2, 4)이다.
  ...
  이런 방식으로 영수가 생각하고 있는 숫자가 될 수 있는 숫자가 총 몇 개인지를 계산해야 한다.

알고리즘

인간이 한다면 쉬운데 이걸 코드로 옮겨서 적으려니 머리가 아프기 시작했다..
이는 브루트포스로 전부 하나씩 다 맞추어 보면서 계산하는 방법을 택했다.
먼저 가능한 세자리 중에서 가장 작은 숫자는 123, 가장 큰 수는 987이다. (반복 사용이 불가함으로)
check라는 배열을 만들어서 불가능한 조합의 숫자는 배제를 해 복잡도를 줄인다.
민혁이가 물어본 숫자랑 123 - 987 중에서 하나씩 다 돌아가보면서 stike, ball이 나올 수 있는 경우의 수를 계산한다. (이게 코드에서 sn, bn)
만약 전부 계산했는데 이 값이 영수가 알려준 strike, ball 값과 다르다면 (둘 중 하나라도) 해당 값은 예측이 불가능해진다.

이를 check 배열에 전부 저장하고 마지막으로 다시 돌아가보면서 해당 배열에 true가 담겨 있는 것의 개수를 세면 이 코드는 끝이 난다.

코드

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

public class Baekjoon2503 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		boolean[] check = new boolean[998];
		
		for (int i=123 ; i<988 ; i++) {
			String num = String.valueOf(i);
			if (num.charAt(0) == '0' || num.charAt(1) == '0' || num.charAt(2) == '0')
				continue;
			if(num.charAt(0) == num.charAt(1) || num.charAt(0) == num.charAt(2) || num.charAt(1) == num.charAt(2))
				continue;
			check[i] = true;
		}
		
		for (int i=0 ; i<N ; i++) {
			st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			for (int a = 123 ; a<988 ; a++) {
				if (check[a]) {
					int sn = 0;
					int bn = 0;
					String numStr = Integer.toString(num);
					String aStr = Integer.toString(a);
					
					for (int one=0 ; one<3 ; one++) {
						for (int two = 0 ; two<3 ; two++) {
							if (numStr.charAt(one) == aStr.charAt(two)) {
								if (one == two) sn++;
								else bn++;
							}
						}
					}
					if (sn != s || bn != b)
						check[a] = false;
				}
			}
		}
		int answer = 0;
		for (int i=123 ; i<988 ; i++) {
			if (check[i]) answer++;
		}
		System.out.println(answer);
	}

}

마무리

생각은 참 쉬운데 코드로 옮겨 적으려면 뇌정지가 오기 시작한다.
이를 해결하기 위해서는 먼저 컴퓨터가 생각하는 방식에 익숙해져야 한다.
논리적인 추론이 가능한 우리와는 다르게 컴퓨터는 하나씩 전부 비교해야 하기 때문..