개강까지 일주일정도 남았는데 너무 할 게 없어서 알고리즘 문제를 풀어보고 있다.

개요

이 문제는 브루트포스로 풀 수 있다. 말이 어려워서 그런데 쉽게 풀어보자면 모든 경우를 다 확인해보는 방법이라고 할 수 있겠다. 마치 우리가 자전거 자물쇠 비밀번호를 까먹어서 3자리수 비번을 각각 0 ~ 9까지 다 해보는 것처럼 말이다. 하지만 이 방법은 시간복잡도가 상당히 높다. 예를 들어서 각각의 자리에는 0부터 9까지의 수가 나올 수 있고 총 3자리수인 수가 있다면 총 경우의 수는 10 * 10 * 10 = 1000이다. 따라서 브루트포스 방식은 모든 문제에 적용시킬 수는 없지만 확인해야 하는 경우의 수가 적다면 이만한 방법도 없기 때문에 문제에 따라 적절한 판단을 내려야 한다.

‘숫자야구’ 문제는 3자리수이면서 각 자리수의 숫자가 서로 다른 수 중에서 적합한 수가 몇 개 있는지 확인하는 문제이다. 조건이 이렇기 때문에 123에서 999 중에 133과 같은 숫자들은 제외하면서 입력으로 주어진 힌트와도 잘 비교해서 풀면 되고 생각보다 경우의 수가 적은 것을 확인할 수 있다. 그래서 우리는 이 문제를 브루트포스로 단순하게 풀 수 있다.

처음 이 문제를 보고선 난 입력으로 주어진 힌트들을 어떻게 조합할지만 고민했었다. 즉, 컴퓨터적인 사고를 하지 못하고 내가 이 문제를 풀었던 방식을 어떻게 하면 알고리즘으로 옮길까만 고민하다 보니 답이 안 나왔다.

풀이

123부터 999까지의 수 중, 서로 다른 숫자 세 개로 구성된 세자리 수를 정답으로 가정을 해놓고 n개의 힌트와 비교해보는 것이다. 반복문을 쭉 돌면서 k번째 힌트와 반복문 변수 i를 비교해보면서 스트라이크와 볼을 계산하고 k번째 힌트의 스트라이크와 볼 개수와 같지 않다면 정답에서 제외하면 된다.

코드

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr);

	bool isNum[1000]{};
	memset(isNum, true, sizeof(isNum));
	for (int i = 123; i <= 999; i++) {
		string inverted = to_string(i);
		if (inverted[0] == inverted[1] || inverted[0] == inverted[2] || inverted[1] == inverted[2]) isNum[i] = false;
		if (inverted[0] - '0' == 0 || inverted[1] - '0' == 0 || inverted[2] - '0' == 0) isNum[i] = false;
	}

	int n;
	cin >> n;
	while (n--) {
		int num, strike, ball;
		cin >> num >> strike >> ball;
		string original = to_string(num);
		for (int i = 123; i <= 999; i++) {
			if (isNum[i] == true) {
				int tStrike{}, tBall{};
				string test = to_string(i);

				for (int j = 0; j < 3; j++) {
					for (int k = 0; k < 3; k++) {
						if (j == k && original[j] == test[k]) tStrike++;
						if (j != k && original[j] == test[k]) tBall++;
					}
				}

				if (strike != tStrike || ball != tBall) isNum[i] = false;
			}
		}
	}

	int count{ 0 };
	for (int i = 123; i <= 999; i++)
		if (isNum[i] == true)
			count++;

	cout << count;

	return 0;
}