개요

[링크]백준 2503번: 숫자 야구

어릴 때 많이 하던 숫자 야구 놀이이다.
입력값으로 몇 가지 숫자, 스트라이크, 볼 값을 주고
답이 될만한 가능성이 있는 숫자가
몇 개인지 출력하는 문제이다.

접근 방식

• 처음 생각
  예를들어 스트라이크 1,볼 1이라고 하자.
  1. 첫 번째 숫자가 스트라이크일때, 두번째 숫자가 볼일 때,
  2. 첫 번째 숫자가 스트라이크일때, 세번째 숫자가 볼일 때,
  3. 두 번째 숫자가 스트라이크일때, 첫번째 숫자가 볼일 때,

  이렇게 쭉 쭉 생각하면 총 6가지 경우의 수가 나온다.
  또, 스트라이크만 1일땐 세가지 경우 생각하고 ,
  이런식으로 입력값의 모든 가짓수를 조합해서 풀어보려했는데
  너무 복잡해서 결국 다른 방법을 찾아보았다.

• 다른 방식
  구글링에서 본 대부분의 방식은
  987까지 담을 수 있는 배열을 선언한 다음,
  123부터 987까지 모든 숫자에 대해
  입력값으로 들어온 조건에 해당하는지 찾아보는 방식이다.

  처음엔 다른 분들이 짠 코드들을 해석했는 데
  123부터 987까지의 모든 숫자와 입력값을 비교한 후
  조건에 맞으면 배열에 체크하는 방식인데,
  이게 이해가 안 되었었다.

  한참 고민 해보니 우리가 찾아야 하는건
  정답의 가능성을 지닌 수로,
  해당 수가 정답이라고 가정했을 때, 입력값으로 들어온 수와 비교했을 때 나온 스트라이크, 볼 갯수가
  입력값으로 들어온 스트라이크,볼의 갯수와 맞아 떨어져야 한다는 걸 깨달았다.

  시간복잡도는 입력값의 갯수가 제일 유의미하게 영향을 끼쳐
  O(n)정도인데 이마저도 최대 100이라서 완전탐색으로 구현해도 상관이 없다고 판단 했다.

코드

#include<iostream>					
#include<vector>
#include<string>
using namespace std;
int arr[1000] = { 0, };				//123부터 987값 가진 배열


typedef struct {					//입력값으로 받고 벡터에 넣어줄 구조체
	string number;					//입력값 숫자(자릿수 계산 용이하게 string값으로)
	int strikes;					//입력값 스트라이크
	int ball;						//입력값 볼
}inputSet;

vector<inputSet> v;					//입력값들 입력할 vector

void input()
{
	inputSet tempSet;				//입력값 구조체 선언
	int amount =0,n=0,s=0,b=0;		//질문 수, 세자리 수,스트라이크.볼
	cin >> amount;
	for (int i = 0; i < amount; i++) {
		cin >> n >> s >> b;
		tempSet.number = to_string(n);
		tempSet.strikes = s;
		tempSet.ball = b;
		v.push_back(tempSet);
	}

}

void solution() {
	for (int i = 123; i <= 987;i++) {			//123부터 987까지
		int str = 0, bal = 0;					//스트라이크,볼 변수
		bool match = true;						//만약 세자리수가 입력값의 조건을 다 만족하는지 체크
		string temp = to_string(i);				//123부터 987의 각 수를 스트링으로
		if (temp[0] - '0' == 0 || temp[1] - '0' == 0 || temp[2] - '0' == 0) continue;		//0은 문제에없으므로 0 제외
		else if (temp[0] == temp[1] || temp[0] == temp[2] || temp[1] == temp[2]) continue;	//서로 다른 세 숫자
		for (int j = 0; j < v.size(); j++) {						//모든 입력값의 수와 비교
			string inputS = v[j].number;							//입력값의 세자리수 string 화
			for (int a = 0; a < 3; a++) {							//조건에 맞는지 검사하려면 i로 들어온 숫자가 
				for (int b = 0; b < 3; b++) {						//정답으로 가정하고 푸는거니
					if (a == b && temp[a] == inputS[b]) str++;		//i숫자와 입력값 수를 비교해서 스트라이크,볼 갯수 비교
					else if (a != b && temp[a] == inputS[b]) bal++;
				}
			}
			if (v[j].strikes != str || v[j].ball != bal) match=false; //하나라도 조건에 안맞으면 match=false가되고 arr[i]는 0으로
			str = 0, bal = 0;										  //초기화
		}
		if (match) arr[i]++;										  //만약 입력값의 조건에 다 해당하면 arr[i]는 1로 바뀜
	}

}
void print() {									//정답 출력 함수
	int sum = 0;								//정답
	for (int i = 123; i <= 987; i++) {
		if (arr[i] > 0)							//1이면
			sum++;								//sum++
	}
	cout << sum;
}
int main() {
	input();
	solution();
	print();
}

문풀후생

처음엔 구조체로 입력받을 생각도 못하고, 그냥
이차원 벡터를 선언하고 두번째 벡터의 template값을
pair로 선언해야하나 생각까지 들었고,
입력값의 각 자리수를 어떻게 다뤄야하나 고민하고
string값으로 넣어서 쓸 생각이 처음에 안 떠올랐다..
아직 갈길이 먼 것 같다.. 더 많이 풀어보고
경험치를 많이 쌓아보자 화이팅