문제
정보문화진흥원 정보 영재 동아리에서 동아리 활동을 하던 영수와 민혁이는 쉬는 시간을 틈타 숫자야구 게임을 하기로 했다.
- 영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324)
- 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 영수에게 묻는다. (예: 123)
- 민혁이가 말한 세 자리 수에 있는 숫자들 중 하나가 영수의 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번으로 센다. 숫자가 영수의 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼 한 번으로 센다.
예) 영수가 324를 갖고 있으면
- 429는 1 스트라이크 1 볼이다.
- 241은 0 스트라이크 2 볼이다.
- 924는 2 스트라이크 0 볼이다.
- 영수는 민혁이가 말한 수가 몇 스트라이크 몇 볼인지를 답해준다.
- 민혁이가 영수의 세 자리 수를 정확하게 맞추어 3 스트라이크가 되면 게임이 끝난다. 아니라면 민혁이는 새로운 수를 생각해 다시 영수에게 묻는다.
현재 민혁이와 영수는 게임을 하고 있는 도중에 있다. 민혁이가 영수에게 어떤 수들을 물어보았는지, 그리고 각각의 물음에 영수가 어떤 대답을 했는지가 입력으로 주어진다. 이 입력을 바탕으로 여러분은 영수가 생각하고 있을 가능성이 있는 수가 총 몇 개인지를 알아맞혀야 한다.
아래와 같은 경우를 생각해보자.
- 민혁: 123
- 영수: 1 스트라이크 1 볼.
- 민혁: 356
- 영수: 1 스트라이크 0 볼.
- 민혁: 327
- 영수: 2 스트라이크 0 볼.
- 민혁: 489
- 영수: 0 스트라이크 1 볼.
이때 가능한 답은 324와 328, 이렇게 두 가지이다.
영수는 동아리의 규율을 잘 따르는 착한 아이라 민혁이의 물음에 곧이곧대로 정직하게 답한다. 그러므로 영수의 답들에는 모순이 없다.
민혁이의 물음들과 각각의 물음에 대한 영수의 답이 입력으로 주어질 때 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수, 이렇게 총 세 개의 정수가 빈칸을 사이에 두고 주어진다.
출력
첫 줄에 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력한다.
예제 입력 1
4
123 1 1
356 1 0
327 2 0
489 0 1예제 출력 1
2문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BJ2503 {
public static class Baseball{
int num,S,B;
public Baseball(int num, int s, int b) {
this.num = num;
S = s;
B = b;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N=Integer.parseInt(br.readLine());
Baseball[] ball=new Baseball[N];
for(int i=0;i<N;i++){
st=new StringTokenizer(br.readLine());
int num=Integer.parseInt(st.nextToken());
int S=Integer.parseInt(st.nextToken());
int B=Integer.parseInt(st.nextToken());
ball[i]=new Baseball(num,S,B);
}
int answer=0;
for(int i=1;i<10;i++){
for(int j=1;j<10;j++){
for(int k=1;k<10;k++){
if(i==j || j==k || k==i) continue;
int number=i*100+j*10+k;
//야구 게임 조건이 맞는지 확인
if(base(number,ball)) answer++;
}
}
}
System.out.println(answer);
}
private static boolean base(int number,Baseball[] ball) {
for(int d=0;d<ball.length;d++){
boolean[] check=new boolean[3];
//strike 개수 만큼 일치하는 숫자들이 있는지
int S_cnt=0;
for(int i=2;i>=0;i--){
int a=ball[d].num/(int)Math.pow(10,i)%10;
int b=number/(int)Math.pow(10,i)%10;
if(a==b) {
S_cnt++;
check[2-i]=true;
}
}
//strike 수가 같지 않으면 false 반환 후 다음 수 체크
if(S_cnt!=ball[d].S) return false;
//ball 개수 만큼 일치하는 숫자들이 있는지(strike한 숫자 제외)
int B_cnt=0;
for(int i=2;i>=0;i--){
//strike 체크 안된 숫자 위치
if(!check[2-i]) {
for (int j = 2; j >=0; j--) {
if(i!=j){
int a=ball[d].num/(int)Math.pow(10,i)%10;
int b=number/(int)Math.pow(10,j)%10;
if(a==b) B_cnt++;
}
}
}
}
if(B_cnt!=ball[d].B) return false;
}
return true;
}
}우리가 아는 숫자 야구의 규칙을 적용하여 정답이 될 수 있는 숫자들의 개수를 출력하는 문제였다.
가장 쉬운 방법은 모든 숫자에 대해 조건이 적용되는지 확인해보는 것이다.
숫자 야구 특성상 0이 들어올 수 없고 같은 숫자가 다시 사용될 수 없기 때문에 123 ~ 987 까지의 숫자들이 입력으로 주어진 strike, ball의 조건을 만족하는지 확인하면 된다.
입력 조건 저장
public static class Baseball{
int num,S,B;
public Baseball(int num, int s, int b) {
this.num = num;
S = s;
B = b;
}
}입력 조건을 저장하기 위해 만든 클래스로 숫자와 그에 따른 strike, ball의 개수를 담는 클래스이다.
모든 경우의 수 체크
for(int i=1;i<10;i++){
for(int j=1;j<10;j++){
for(int k=1;k<10;k++){
if(i==j || j==k || k==i) continue;
int number=i*100+j*10+k;
//야구 게임 조건이 맞는지 확인
if(base(number,ball)) answer++;
}
}
}문제의 조건에서 숫자는 무조건 세자리 수이기 때문에 3중 for문을 이용하여 모든 숫자의 경우를 체크한다. 이때, 같은 숫자는 반복되지 않도록 조건을 걸어준다.
모두 다른 숫자가 선택되었다면 100의 자리, 10의 자리, 1의 자리 수로 만들어주어 하나의 세자리 숫자를 만들어주고 입력으로 주어진 조건을 모두 만족하는지 확인한다.
입력 조건 확인
private static boolean base(int number,Baseball[] ball) {
for(int d=0;d<ball.length;d++){
boolean[] check=new boolean[3];
//strike 개수 만큼 일치하는 숫자들이 있는지
int S_cnt=0;
for(int i=2;i>=0;i--){
int a=ball[d].num/(int)Math.pow(10,i)%10;
int b=number/(int)Math.pow(10,i)%10;
if(a==b) {
S_cnt++;
check[2-i]=true;
}
}
//strike 수가 같지 않으면 false 반환 후 다음 수 체크
if(S_cnt!=ball[d].S) return false;
//ball 개수 만큼 일치하는 숫자들이 있는지(strike한 숫자 제외)
int B_cnt=0;
for(int i=2;i>=0;i--){
//strike 체크 안된 숫자 위치
if(!check[2-i]) {
for (int j = 2; j >=0; j--) {
if(i!=j){
int a=ball[d].num/(int)Math.pow(10,i)%10;
int b=number/(int)Math.pow(10,j)%10;
if(a==b) B_cnt++;
}
}
}
}
if(B_cnt!=ball[d].B) return false;
}
return true;
}입력으로 받은 야구 게임 조건의 개수만큼 반복문을 돌린다.
차례대로 strike의 개수를 확인하고 ball의 개수를 확인한다.
이때, strike를 체크하고 같은 위치라고 판단된 숫자는 ball의 조건을 확인하면 안되기 때문에 boolean을 통해 strike 조건을 만족한 숫자를 표시해준다.
int형 숫자로 받아왔기 때문에 한 자리씩 확인하기 위해서는 계산을 해야하는데
num/(int)Math.pow(10,i)%10
을 이용하면 한 자리씩 계산할 수 있다.
예를 들면)
123이라는 숫자를 하나씩 확인하기 위해서는123/100 = 1을 하여 100의 자리를 구하고
123/10 = 12->12%10 = 2를 하여 10의 자리를 구한다.
즉, 10의 자리를 구하기 위해서는123/10%10을 차례로 계산해야한다.
그렇다면 1의 자리를 구하기 위한 수식은123/1%10 = 3이 된다.
같은 숫자이고 같은 위치라면 strike의 개수를 구하기 위한 S_cnt를 증가한다.
또한 strike 위치를 체크해야하기 때문에 boolean 배열의 [2-i] 인덱스에 표시해준다.
for문의 i 변수가 반대로 감소하기 때문이다!
strike 개수를 모두 확인하고 입력 조건의 strike 수와 다르다면 false를 반환하고 같다면 ball의 조건을 확인한다.
ball의 조건 또한 strike 조건을 확인한 것과 같은 방식으로 숫자를 하나씩 뽑아서 확인하면되는데 ball은 위치가 달라도 상관없기 때문에 number의 숫자 위치 하나하나를 모두 확인하여 같은 숫자가 있는지 봐야한다.
같은 숫자가 있다면 ball의 개수를 구하기 위한 B_cnt를 증가한다.
역시 조건의 ball 개수와 다르다면 false를 return하고 같다면 다음 조건을 확인한다.
모든 조건을 만족한다면 해당 숫자는 정답이 될 수 있는 숫자라고 판단하고 true를 반환하여 최종 답인 answer의 수를 증가한다.
모든 경우의 수를 체크해야하는 단순한 방법을 떠올리지 못해 로직을 짜는데 시간이 걸렸다.
어차피 세 자리 수로 제한되어있기 때문에 완전탐색을 통해 모든 경우를 체크해도 문제가 없었다.!
모든 경우의 수를 체크한다는 것을 깨닫고 나면 각 입력 조건을 만족하는지 어떻게 확인할 것인지가 관건이다.
이 부분은 구현이었기 때문에 문제 조건을 확인하고 하나씩 짜다보면 금방 완성할 수 있었다.
