문제
숫자 야구 게임이란 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~9로 모든 숫자들 만들기
- 주어진 질문들에 맞는지 숫자야구 해보기.
우선 순열을 만드는 방법은 다음과 같다.
재귀함수를 사용하여 순열을 만들었는데,
스왑을 통해서 선택된 것을 앞으로, 안된것들을 뒤로 몰아넣은 뒤 ,
원하는 깊이만큼 (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;
}
}
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++;
}
}
}
'알고리즘 > 문제풀이' 카테고리의 다른 글
네트워크 (프로그래머스) [JAVA] (0) | 2020.12.27 |
---|---|
카펫 (프로그래머스) [JAVA] (0) | 2020.12.27 |
소수찾기 (프로그래머스) [JAVA] (0) | 2020.12.27 |
모의고사 (프로그래머스) [JAVA] (0) | 2020.12.27 |
양자화 (알고스팟 QUNATIZE) [JAVA] (0) | 2020.12.27 |
Comment