[백준] 2503번 숫자 야구

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q2000/Q2503.java

숫자 야구의 조건을 준다.(숫자 스트라이크 볼) 예를 들어 다음과 같다.
4
123 1 1
356 1 0
327 2 0
489 0 1

조건이 주어졌을 때, 해당 몇 개의 숫자가 답의 후보가 될 수 있는지를 작성하여라.

처음 생각

스트라이크와 볼의 개수를 계속적으로 따져주면서 특정 후보를 지어도 되지만 숫자 야구의 숫자는 중복이 불가능하므로 생각보다 봐야되는 개수가 적다.

▶ 중복이 불가능한 것은 111 112 같이 3숫자 안에 동일 숫자가 들어있으면 안된다.

다음 생각

따라서 숫자 야구로 쓰일 수 있는 모든 숫자를 만들어 조건으로 주어진 숫자들과 비교해 모두 만족하면 결과값을 +1 시켜주었다.

▶ 재귀를 이용해서 사용할 숫자들을 골라주었다. 중복된 수가 사용되면 안되므로 방문 표시 배열과 숫자를 택할 배열을 각각 선언해주었다.

▶ 처음에는 방문 배열 하나로 숫자까지 만들려고 하였는데 3개의 숫자가 모아졌을 때 순서대로 만들기가 어려워서 바꿔주었다. 방문 배열(1~9)를 반복문으로 탐색해서 1값이 들어있으면 사용한 숫자로 판단하여 3자리 숫자를 만드는데 사용해 주려고 하였는대, 반복문이 무조건 0부터 읽으니 123을 위한 방문표시와 132를 위한 방문표시가 같아져 발생한 일이였다.

방안

1) 주어진 개수가 적다면 브루트 포스 즉, 완전 탐색이 이상적인 방안인 것 같다.

package baekjoon.q2000;
 
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Q2503 {
    static List<Pair> list = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // 상태 담아 놓기
        for(int i=0;i<n;i++)
            list.add(new Pair(sc.next(),sc.nextInt(),sc.nextInt()));
        // 조합 만들기
        solve(0);
        System.out.println(result);
    }
    
    static int result;
    static int[] arr = new int[3];
    static int[] visited = new int[10];
    private static void solve(int cnt) {
        if(cnt==3) {
            // 문자 만들기
            String n = "";
            for(int i=0;i<3;i++)
                n += arr[i];
            // 조건 들과 다 비교
            for(Pair t:list) {
                int s=0,b=0;
                for(int i=0;i<3;i++) {
                    if(n.charAt(i)==t.n.charAt(i)) s++;
                    else if(t.n.contains(n.charAt(i)+"")) b++;
                }
                if(t.s==s && t.b==b) continue;
                return;
            }
            result++;            
            return;
        }
        
        for(int i=1;i<=9;i++) {
            // 이미 선택된 번호면 패스
            if(visited[i]==1) continue;
            // 해당 번호 선택
            arr[cnt] = i;
            visited[i] = 1;
            solve(cnt+1);
            visited[i] = 0;
            // 해당 번호 미선택
        }
    }
    
    static class Pair{
        private int s,b;
        private String n;
        Pair(String n,int s,int b){
            this.n = n;
            this.s = s;
            this.b = b;
        }
    }
}