[백준] 2503번 - 숫자 야구 java

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

 

난이도 : S3

Tag : Simulation

풀이 일자 : 2025-03-12

---

문제 탐색하기

• 영수가 생각한 수: 111 ~ 999 (0 제외, 중복 숫자 없음)
• 민혁이가 질문한 수: 111 ~ 999 (0 제외, 중복 숫자 없음)
• N: 질문의 수 (1 <= N <= 100)
• 스트라이크 (Strike): 같은 숫자가 같은 위치에 존재할 경우
• 볼 (Ball): 같은 숫자가 존재하지만, 위치가 다를 경우

민혁이가 질문을 하고 영수가 대답한 정보를 파악해서 답이 될 수 있는 숫자의 개수를 출력해야 합니다.

이때, 각 숫자는 서로 달라야 합니다.

가능한 시간복잡도

문제에 요구하는대로 구현하는 시뮬레이션 문제입니다.

먼저 숫자는 1부터 9까지로 이루어진 서로다른 3자리의 수 입니다.

그럼 모든 경우의 수는 9*8*7로 대략 500개를 탐색하게 됩니다.

그리고 각 숫자가 영수와 민혁의 문답에 모두 일치하는지도 확인해야 합니다.

 

최대 100번까지 질문이 가능하다고 했으므로 

하나의 숫자에 100번의 질문을 파악한다면 500*100으로 O(50000)의 시간복잡도가 걸리게 됩니다.

시간 제한 1초인 1억번안에 들어가므로 충분히 안정된 풀이를 할 수 있습니다.

 

알고리즘 선택

저는 완전탐색으로 풀어보도록 하겠습니다.

1. 111~999까지의 모든 숫자 후보 생성합니다. (0 포함 X, 중복 없는 3자리 숫자)
2. 각 숫자가 모든 질문을 만족하는지 확인합니다.
3. 모든 질문을 만족하는 숫자 개수를 출력합니다.

이때, 스트라이크와 볼의 판단 기준은 아래와 같습니다.

• 같은 위치에 같은 숫자가 존재하면 스트라이크
• 같은 숫자가 존재하지만, 위치가 다르면 볼

---

코드 설계하기

1. 입력을 미리 저장
   • 질문이 최대 100개까지 주어지므로, List에 저장해서 재사용
2. 가능한 모든 숫자(111~999)를 순회하며 검사
   • 0 포함 X, 중복 숫자 X인 숫자만 고려
3. 각 숫자가 모든 질문을 만족하는지 확인
   • 스트라이크, 볼 개수 비교 
4. 가능한 숫자 개수를 출력

---

정답코드

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        List<String[]> questions = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
            int strike = Integer.parseInt(st.nextToken());
            int ball = Integer.parseInt(st.nextToken());
            questions.add(new String[]{s, String.valueOf(strike), String.valueOf(ball)});
        }
        
        int ans = 0;

        for(int num = 111; num <1000; num++){
            String currNum = Integer.toString(num);
            if(currNum.contains("0") || hasDuplicate(currNum))continue;

            boolean isPossible = true;
            for (String[] query : questions) {
                String s = query[0];
                int strike = Integer.parseInt(query[1]);
                int ball = Integer.parseInt(query[2]);

                if (!Check_num(currNum, s, strike, ball)) {
                    isPossible = false;
                    break;
                }
            }
             if (isPossible) ans++;
        }
        System.out.println(ans);
    }
    
    public static boolean Check_num(String currNum, String num, int s, int b){
        int strike = 0, ball = 0;

        for (int i = 0; i < 3; i++) {
            if (currNum.charAt(i) == num.charAt(i)) {
                strike++;
            }
        }

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i != j && currNum.charAt(i) == num.charAt(j)) {
                    ball++;
                }
            }
        }
        return (strike == s && ball == b);
    }

    public static boolean hasDuplicate(String num) {
        return num.charAt(0) == num.charAt(1) || num.charAt(1) == num.charAt(2) || num.charAt(0) == num.charAt(2);
    }
}