설명
이번 문제는 숫자 야구 게임과 관련된 문제로 후보 숫자를 추려내는 방식으로 접근해야 한다. 처음에는 어떻게 풀어야 할지 조금 고민이 많았다.
우선 입력된 질문을 저장하기 위해 nums[], strikes[], balls[] 배열을 만들었다. nums[]에는 민혁이 질문한 숫자를 strikes[]와 balls[]에는 각각 영수가 답한 스트라이크 수와 볼 수를 저장한다.
다음으로는 후보 숫자를 생성한다. 문제의 조건상 후보 숫자는 1~9 사이의 서로 다른 세 자리 숫자이므로 123부터 987까지 모든 숫자를 반복문으로 검사한다. 이때 각 자리 숫자를 비교해야 하므로 후보 숫자를 문자열(String)로 변환한다. 그리고 여기서 주의할 점이 있다.
숫자에 0이 포함되어 있으면 후보에서 제외한다.
세 자리 중 같은 숫자가 중복되면 후보에서 제외한다.
이렇게 조건을 만족하는 후보 숫자에 대해서만 체크를 진행한다. 후보가 가능한지 확인하는 변수 check를 만들고 모든 질문과 비교한다. 질문 숫자 역시 문자열로 변환하여 각 자리별로 비교한다.
여기서 중요한 부분이 스트라이크와 볼을 계산하는 로직이다. 후보 숫자와 질문 숫자의 각 자리(x, y)를 비교한다. 만약 후보 숫자 x번째 자리와 질문 숫자 y번째 자리가 같은 숫자라면,
x와 y가 같으면 스트라이크
x와 y가 다르면 볼
이렇게 계산한다.
여기서 "정답을 모르는데 어떻게 판단하는가?" 하는 의문이 있을 수 있다.
사실 우리는 후보 숫자가 정답인지 모르지만 입력된 질문과 영수의 답을 기준으로 후보가 가능한지 확인하는 것이다. 즉 정답인지 아닌지는 모른다. 하지만 후보 숫자가 질문에 대한 스트라이크/볼 규칙을 모두 만족하면 가능성 있는 정답으로 보는 것이다.각 질문과 비교하여 계산한 스트라이크와 볼이 입력된 스트라이크/볼과 다르면 그 후보는 불가능하므로 제외한다. 모든 질문을 통과하면 후보 숫자는 가능성이 있는 정답으로 간주하고 최종 카운트에 포함시킨다.
즉 이 문제의 핵심은 정답을 직접 아는 것이 아니라 후보 숫자가 모든 입력 조건을 만족하는지 체크하는 완전 탐색 방식이라는 점이다. 정답을 모르는 상황에서도 후보가 질문과 답을 모두 만족하면 가능성이 있는 정답으로 처리할 수 있다.
시간복잡도:O(N), 공간복잡도:O(N)
회독
- [ x ] 1회
- 2회
- 3회
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [] nums = new int[n];
int [] strikes = new int[n];
int [] balls = new int[n];
for(int i=0;i<n;i++){
StringTokenizer st = new StringTokenizer(br.readLine());
nums[i]= Integer.parseInt(st.nextToken());
strikes[i] = Integer.parseInt(st.nextToken());
balls[i] = Integer.parseInt(st.nextToken());
}
int count = 0;
// 후보숫자 123~987
for(int i=123;i<=987;i++){
String s = Integer.toString(i);
if(s.contains("0") || s.charAt(0)==s.charAt(1)||
s.charAt(0)==s.charAt(2) || s.charAt(1)==s.charAt(2)) continue;
boolean check = true;
// 질문 숫자
for(int j=0;j<n;j++){
String ss = Integer.toString(nums[j]);
int strike = 0, ball = 0; //현재 스트라이크, 볼 초기화
for(int x=0;x<3;x++){ // 후보 숫자 자리 반복
for(int y=0;y<3;y++){ // 질문 숫자 자리 반복
if(s.charAt(x)==ss.charAt(y)){
if(x==y) strike++;
else ball++;
}
}
}
if(strike!=strikes[j] || ball!=balls[j]){
check = false;
break;
}
}
if(check) count++;
}
System.out.println(count);
}
}
다른 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] guesses = new int[n][3];
int[] strikes = new int[n];
int[] balls = new int[n];
for(int i = 0; i < n; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
String num = st.nextToken();
guesses[i][0] = num.charAt(0) - '0';
guesses[i][1] = num.charAt(1) - '0';
guesses[i][2] = num.charAt(2) - '0';
strikes[i] = Integer.parseInt(st.nextToken());
balls[i] = Integer.parseInt(st.nextToken());
}
int answer = 0;
for(int i = 1; i <= 9; i++){
for(int j = 1; j <= 9; j++){
if(j == i) continue;
for(int k = 1; k <= 9; k++){
if(k == i || k == j) continue;
int[] candidate = {i, j, k};
boolean possible = true;
for(int g = 0; g < n; g++){
int s = 0, b = 0;
for(int x = 0; x < 3; x++){
if(candidate[x] == guesses[g][x]) s++;
else if(candidate[x] == guesses[g][(x+1)%3] || candidate[x] == guesses[g][(x+2)%3]) b++;
}
if(s != strikes[g] || b != balls[g]){
possible = false;
break;
}
}
if(possible) answer++;
}
}
}
System.out.println(answer);
}
}