[백준]JAVA - 2503번: 숫자 야구

https://www.acmicpc.net/problem/2503

2503번: 숫자 야구

풀이

브루트포스, 구현 문제는 개인적으로 너무 어렵다..

나만의 팁이라고 한다면 dp처럼 공책에다가 써본 후에 로직을 어느 정도 파악하고 코딩을 시작한다.

 

위 문제의 조건은 아래와 같다.

1. 범위는 세 자릿수
2. 자릿수와 숫자가 같으면 스트라이크
3. 자릿수가 다르고, 숫자가 같은 게 있으면 볼

그럼 이제 문제를 풀어보겠다.

 

[1번 조건]

세 자릿수를 가진 자연수는 100 부터 999 이다. 

하지만 중복된 숫자와 0이 들어가면 안되기 때문에 범위는 123 부터 987 이다.

for (int i=123; i<988; i++) {
    int a2 = i / 100;            // 100의 자리
    int b2 = i / 10 - (a2 * 10); // 10의 자리
    int c2 = i % 10;             // 1의 자리
            
    // 0이 포함되거나 중복된 수가 있는 경우
    if (a2 == 0 || b2 == 0 || c2 == 0 || a2 == b2 || a2 == c2 || b2 == c2)  continue;
            
    if (find(a2, b2, c2)) {
        cnt++;
    }
}

 

[2, 3번 조건]

해당 범위를 돌면서 민혁이가 질문한 숫자, 스트라이크, 볼이 같으면 영수가 생각한 숫자의 후보가 된다.

public static boolean find(int a2, int b2, int c2) {
    for (int i=0; i<arrList.size(); i++) {
        Number number = arrList.get(i);
            
        int a1 = number.num / 100;            // 100의 자리
        int b1 = number.num / 10 - (a1 * 10); // 10의 자리
        int c1 = number.num % 10;             // 1의 자리
            
        int st1 = number.strike;
        int ba1 = number.ball;
            
        int st2 = 0;
        int ba2 = 0;
 
        // 스트라이크
        if (a1 == a2) st2++;
        if (b1 == b2) st2++;
        if (c1 == c2) st2++;
            
        // 볼
        if (a2 == b1 || a2 == c1) ba2++;
        if (b2 == a1 || b2 == c1) ba2++;
        if (c2 == a1 || c2 == b1) ba2++;
            
        if (st1 != st2 || ba1 != ba2) {
            return false;
        }
    }
    return true;
}

 

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {
    static ArrayList<Number> arrList;
    
    public static class Number {
        int num;
        int strike;
        int ball;
        
        public Number (int num, int strike, int ball) {
            this.num = num;
            this.strike = strike;
            this.ball = ball;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        
        arrList = new ArrayList<>();
        
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            
            int n = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            arrList.add(new Number(n, s, b)); // 질문
        }
        
        int cnt = 0;
        for (int i=123; i<988; i++) {
            int a2 = i / 100;            // 100의 자리
            int b2 = i / 10 - (a2 * 10); // 10의 자리
            int c2 = i % 10;             // 1의 자리
            
            // 0이 포함되거나 중복된 수가 있는 경우
            if (a2 == 0 || b2 == 0 || c2 == 0 || a2 == b2 || a2 == c2 || b2 == c2)  continue;
            
            if (find(a2, b2, c2)) {
                cnt++;
            }
        }
 
        System.out.println(cnt);
    }
    
    public static boolean find(int a2, int b2, int c2) {
        for (int i=0; i<arrList.size(); i++) {
            Number number = arrList.get(i);
            
            int a1 = number.num / 100;            // 100의 자리
            int b1 = number.num / 10 - (a1 * 10); // 10의 자리
            int c1 = number.num % 10;             // 1의 자리
            
            int st1 = number.strike;
            int ba1 = number.ball;
            
            int st2 = 0;
            int ba2 = 0;
 
            // 스트라이크
            if (a1 == a2) st2++;
            if (b1 == b2) st2++;
            if (c1 == c2) st2++;
            
            // 볼
            if (a2 == b1 || a2 == c1) ba2++;
            if (b2 == a1 || b2 == c1) ba2++;
            if (c2 == a1 || c2 == b1) ba2++;
            
            if (st1 != st2 || ba1 != ba2) {
                return false;
            }
        }
        
        return true;
    }
}

내가 생각한 시간 복잡도: O(864N)