백준 2503 숫자야구(Silver3)

정답코드

import java.util.*;


public class Main {

	static int[][] digit;
	static int [][] score;
	static int N;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		

		digit = new int[N][3];
		score = new int[N][2];

		for(int i = 0; i < N; i++) {
			
			int num = sc.nextInt();
			
			digit[i][0] = num/100;
			digit[i][1] = (num - digit[i][0]*100)/10;
			digit[i][2] = (num - digit[i][0]*100 - digit[i][1]*10);
			
			
			score[i][0] = sc.nextInt();  //strike
			score[i][1] = sc.nextInt();  //ball 
		}
		
		System.out.println(compute_case());
	
	}
	
	public static int compute_case() {
		
		int result = 0;
		for(int i = 1; i <= 9; i++) {
			for(int j = 1; j <= 9; j++) {
				if(i != j) {
					for(int k = 1; k <= 9 ; k++) {
						//3자리 숫자가 모두 중복이 안 되는 경우만 생각 
						if(i!=k && j!=k) {
							boolean flag = true;
							for(int n = 0; n < N; n++) {
								int strike = 0;
								int ball = 0;

								//첫 번째 숫자 
								if(i == digit[n][0])strike++;
								else if(i == digit[n][1]||i == digit[n][2])ball++;
								
								//두 번째 숫자 
								if(j == digit[n][1])strike++;
								else if(j == digit[n][0]||j == digit[n][2])ball++;
								
								//세 번째 숫자 
								if(k == digit[n][2])strike++;
								else if(k == digit[n][0]||k == digit[n][1])ball++;
								
								
								//계산한 s,b 값과 실제 값이 다르면 break
								if(strike != score[n][0] || ball != score[n][1])	{
									flag = false;
									break;
								}

							}
							
							if (flag == true)result++;
						}

					}
				}
					
			}
		}
		
		return result;
		
	}
}

전략

• 처음에는 받은 수를 바탕으로 백트래킹을 거쳐서 경우의 수를 줄이고 문제를 풀려고 했음
• 그러나 경우의 수가 너무 많고 일일이 저장하는 것이 매우 복잡
• 브루트포스의 기본으로 돌아가자 하나씩 모두 살펴보는 경우로
• 123 ~ 987까지 수를 보면서 Strike, Ball을 판별하고 맞는 경우를 찾는다
• 실제로 시간 복잡도도 9 x 8 x 7 x 3 ... 정도 밖에 안 돼서 시간도 여유로운 문제
• 시간 복잡도상 브루트포스로 간단히 풀 수 있는 문제라면 그냥 쉬운길을 택하자