숫자 야구 게임 - 완전 탐색

숫자 야구 게임에서 정답이 될 수 있는 숫자 조합의 개수를 출력

 

주어진 힌트를 가지고 정답이 될 수 있는 숫자의 조합을 모두 찾는 문제이다. 완전 탐색으로 모든 조합을 찾아 낼 수 있으면 쉽게 풀 수 있다.

 

모든 숫자를 순회하면서 각 숫자조합 마다 힌트와 일치하는지 검사한다. 주어진 힌트(strike 숫자, ball 숫자)들과 완전히 개수가 일치하면 정답 중 하나라는 뜻이다.

 

문제의 핵심

1. 어느 숫자가 힌트의 모든 조건과 일치하면 정답이다.
2. 문제를 해결하는데 정답을 가정하고 역순으로 접근하는 방법도 도움이 된다.

 

int solution(vector<vector<int>> baseball)
{
	int answer = 0;
	// 야구게임에서 사용 할 수 있는 모든 경우의 수
	for(int i = 123; i <= 987; ++i)	
	{
		vector<int> digits;
		digits.push_back(i/100); // 100의 자리수
		digits.push_back(i%100/10); // 10의 자리수
		digits.push_back(i%100%10); // 1의 자리수

		if(!digits[1] || !digits[2] || digits[0] == digits[1] || digits[1] == digits[2] || digits[2] == digits[0]) continue;

		int count = 0;
		for(auto it : baseball)
		{
			int strikes = 0;
			int balls = 0;

			int q = it[0];
			vector<int> qDigits;
			qDigits.push_back(q / 100); // 100의 자리수
			qDigits.push_back(q % 100 / 10); // 10의 자리수
			qDigits.push_back(q % 100 % 10); // 1의 자리수

			for(int i = 0; i < 3; ++i)
			{
				if(digits[i] == qDigits[i]) ++strikes;
				else if(digits[i] == qDigits[(i+1)%3] || digits[i] == qDigits[(i+2)%3]) ++balls;
			}
			
			if(it[1] == strikes && it[2] == balls) ++count;
			
		}

		if(count == baseball.size())
			++answer;	
	}

	return answer;
}