숫자 야구 (프로그래머스) [JAVA]
반응형

 

문제

숫자 야구 게임이란 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의 각 행은 [세 자리의 수, 스트라이크의 수, 볼의 수] 를 담고 있습니다.

입출력 예

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

 

풀이

역시 2가지 문제로 나눠서 생각했다.

  1. 1~9로 모든 숫자들 만들기
  2. 주어진 질문들에 맞는지 숫자야구 해보기.

우선 순열을 만드는 방법은 다음과 같다.

재귀함수를 사용하여 순열을 만들었는데,

스왑을 통해서 선택된 것을 앞으로, 안된것들을 뒤로 몰아넣은 뒤 ,

원하는 깊이만큼 (nPr에서 r) 재귀호출해서 뽑아주는 방식이다.

ex) 1 2 3 에서 2개

depth = 0, i = 0에서 1선택

​ -> depth = 1, i=1에서 2 선택 (1,2) or depth = 1, i = 2해서 3선택 (1,3)

depth = 0, i = 1에서 2선택 후 swap (2,1,3)

​ -> depth = 1, i = 1에서 1선택 (2,1) or depth = 1, i = 2 해서 3선택 (2,3)

depth = 0, i =2 에서 3선택 후 swap(3,1,2)

​ -> depth = 1, i = 1에서 1선택 (3,1) or depth = 1, i = 2 해서 3선택 (3,2)

숫자야구 판별은 각 문제마다 strike와 ball 개수를 확인한 후, 모든 숫자를 비교해 문제에 맞는지 아닌지 파악했다.

시간복잡도는 모든 부분집합을 만드는데 $O( 9^3 )$, 숫자야구 체크하는데 $O( 9N )$ 으로 $O( 9^4N )$이다.

 

코드

public class Main {
	public static StringBuilder sb = new StringBuilder();
    public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    public static void main(String[] args)throws Exception {
    	Solution s = new Solution();
    	int[][] baseball = {{123,1,1},{356,1,0},{327,2,0},{489,0,1}};
    	System.out.println(s.solution(baseball));
    	
    }
}
class Solution {
	int answer = 0;
	public int solution(int[][] baseball) {
        int[] res = new int[3];
        int[] arr = {1,2,3,4,5,6,7,8,9};
        perm(baseball,res,arr.length,res.length,arr,0);
        return answer;
    }
	
	public void swap(int[]arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	public void parse(int[] num, int number) {
		for(int i=num.length-1; i>=0; i--) {
			num[i] = number%10;
			number = number/10;
		}
	}
	
	public void perm(int[][] baseball, int[] res, int n, int r, int[] arr, int depth) {
		if(depth == r) {
			if(BallTest(res,baseball)) {
				System.out.println(res[0]+" "+res[1]+" "+res[2]);
				answer++;
			}
			return;
		}
		
		for(int i= depth; i<n; i++) {
			swap(arr,depth,i);
			res[depth] = arr[depth];
			perm(baseball,res,n,r,arr,depth+1);
			swap(arr,depth,i);
		}
	}
	
	public boolean BallTest(int[] res, int[][] baseball) {
		int[] num;
		boolean result = true;
		for(int i=0; i<baseball.length; i++) {
			num = new int[3];
			parse(num, baseball[i][0]);
			int strike = baseball[i][1];
			int ball = baseball[i][2] + strike; //동시에 뺄꺼라서
			
			for(int a =0; a<res.length; a++) {
				if(res[a] == num[a]) strike--;
				for(int b=0; b<num.length; b++) {
					if(res[a] == num[b]) ball--;
				}
			}
			if(strike != 0 || ball != 0) {
				result = false;
				break;
			}
		}
		return result;
	}
}

 

결과

테스트 1 〉통과 (1.65ms, 52.2MB)
테스트 2 〉통과 (1.74ms, 50.7MB)
테스트 3 〉통과 (1.70ms, 50.2MB)
테스트 4 〉통과 (1.87ms, 54.1MB)
테스트 5 〉통과 (1.60ms, 52.1MB)
테스트 6 〉통과 (1.58ms, 53MB)
테스트 7 〉통과 (1.64ms, 52.9MB)
테스트 8 〉통과 (1.57ms, 52.4MB)
테스트 9 〉통과 (1.60ms, 52.4MB)
테스트 10 〉통과 (1.54ms, 52.3MB)

 

복기

나는 1~9라는 카드로 3자리 수를 만든다고 생각해 순열을 사용했으나,

숫자의 범위가 정해져있고, 간단하므로 그냥 이렇게 하는게 더 쉬울 것 같다는 생각도 들었다.

for(b[0] = 1; b[0] < 10; b[0]++){
            for(b[1] = 1; b[1] < 10; b[1]++){
                if(b[0] == b[1]) continue;
                for(b[2] = 1; b[2] < 10; b[2]++){
                    if(b[0] == b[2] || b[1] == b[2]) continue;
                    if(match(b, a)) ret++;
                }
            }
}

 

반응형