[프로그래머스] 숫자 야구

문제 설명

숫자 야구 게임이란 2명이 서로가 생각한 숫자를 맞추는 게임입니다. 게임해보기

각자 서로 다른 1~9까지 3자리 임의의 숫자를 정한 뒤 서로에게 3자리의 숫자를 불러서 결과를 확인합니다. 그리고 그 결과를 토대로 상대가 정한 숫자를 예상한 뒤 맞힙니다.

* 숫자는 맞지만, 위치가 틀렸을 때는 볼 * 숫자와 위치가 모두 맞을 때는 스트라이크 * 숫자와 위치가 모두 틀렸을 때는 아웃

예를 들어, 아래의 경우가 있으면

A : 123 B : 1스트라이크 1볼. A : 356 B : 1스트라이크 0볼. A : 327 B : 2스트라이크 0볼. A : 489 B : 0스트라이크 1볼.

이때 가능한 답은 324와 328 두 가지입니다.

질문한 세 자리의 수, 스트라이크의 수, 볼의 수를 담은 2차원 배열 baseball이 매개변수로 주어질 때, 가능한 답의 개수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 질문의 수는 1 이상 100 이하의 자연수입니다.
• baseball의 각 행은 [세 자리의 수, 스트라이크의 수, 볼의 수] 를 담고 있습니다.

입출력 예

baseballreturn

[[123, 1, 1], [356, 1, 0], [327, 2, 0], [489, 0, 1]]

2

---

숫자 야구의 질문이 들어오면 가능한 수가 몇 개나 있는지 구하는 문제이다.

완전 탐색으로 쉽게 해결할 수 있다.

dfs를 이용해서 모든 가능한 수를 만든 후, 세자리가 되었을 때, 스트라이크와 볼의 개수를 파악해서 같다면 true, 다르면 false를 반환한다. 모든 질문의 답이 true라면 cnt를 1 증가한다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Programmers/%EC%88%AB%EC%9E%90%20%EC%95%BC%EA%B5%AC.cpp

chosh95/STUDY

C++ 코드

#include <string>
#include <iostream>
#include <vector>

using namespace std;

int cnt;
int visit[10];

bool isPossible(int ballIdx, string str, vector<vector<int>> baseball) {
	int strike = 0, ball = 0;
	int qStrike = baseball[ballIdx][1];
	int qBall = baseball[ballIdx][2];
	string qStr = to_string(baseball[ballIdx][0]);

	for (int i = 0; i < 3; i++) {
		if (str[i] == qStr[i]) 
			strike++;
		else if (qStr.find(str[i])!=string::npos) 
			ball++;
	}
	if (strike == qStrike && ball == qBall) return true;
	return false;
}

void dfs(int idx, string str, vector<vector<int>> baseball) {
	if (idx == 3) {
		for (int i = 0; i < baseball.size(); i++) {
			if (!isPossible(i, str, baseball)) {
				return;
			}
		}
		cnt++;
		return;
	}
	for (int i = 1; i <= 9; i++) {
		if (visit[i] == 1) continue;
		visit[i] = 1;
		str += to_string(i);
		dfs(idx + 1, str, baseball);
		visit[i] = 0;
		str.erase(idx);
	}
}

int solution(vector<vector<int>> baseball) {
	int answer = 0;
	
	dfs(0, "", baseball);
	answer = cnt;
	return answer;
}

int main()
{
	cout << solution({ {123,1,1},{356,1,0},{327,2,0},{489,0,1} });
}