[백준/Java] 2503번 : 숫자 야구

✏️ 문제 분석

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

 

게임 룰 : 

영수가 생각한 숫자를 민혁이가 맞춰야 한다.

두 사람이 부른 세 자리 숫자(1~9로 구성, 서로 다른 세 숫자)를 비교하여

• 값과 위치가 모두 같으면 스트라이크
• 값은 같은데 위치가 다르면 볼

3스트라이크가 되면 게임 끝

아니면 다시 게임 진행

 

구해야할 것 :

민혁이가 부른 숫자와 영수의 대답을 가지고

영수가 생각한 숫자일 가능성이 있는 수가 총 몇 개인지 구하라.

영수의 답에는 모순이 없다고 가정한다.

✏️ 구현 아이디어

• 민혁: 123
• 영수: 1 스트라이크 1 볼.
• 민혁: 356
• 영수: 1 스트라이크 0 볼.
• 민혁: 327
• 영수: 2 스트라이크 0 볼.
• 민혁: 489
• 영수: 0 스트라이크 1 볼.

👉🏻첫 번째 게임

영수가 생각할 수 있는 숫자는 123~987 사이

123~987에 해당하는 모든 수를 123과 비교하여 스트라이크 1, 볼 1을 만족하는지 확인하고

만족한다면 그 숫자를 유효한 숫자로 취급한다. 

 

예)

123과 123 비교 : 스트라이크3 볼0 -> 유효한 숫자 x

123과 124 비교 : 스트라이크2 볼0 -> 유효한 숫자 x

...

123과 324 비교 : 스트라이크1 볼1 -> 유효한 숫자 o

...

123과 987 비교 : 스트라이크0 볼0 -> 유효한 숫자 x

 

👉🏻두 번째 게임

123~987에 해당하는 모든 수를 356과 비교하여 스트라이크 1, 볼 0을 만족하는지 확인하고

만족한다면 그 숫자를 유효한 숫자로 취급한다. 

...

 

마지막 4번째 게임까지 완료하고 나면, 각 게임에서 유효한 숫자들을 모두 취합한다.

네 게임 모두에서 유효하다고 판단된 숫자가 몇 개인지 출력한다.

 

✏️ 알고리즘

구현 문제이다. 브루트 포스로 모든 경우를 검사한다.

✏️ 시간 복잡도

N번 검사할 때마다 모든 유효한 숫자를 비교하므로 연산은 N*865번 발생.

N의 최대값은 100이므로 최대 86,500번 연산. 제한 시간 안에 실행 가능하다.

✏️ 코드 설계

1. 숫자 입력받기
2. 유효한 숫자가 몇 번 선정되었는지 저장하는 배열 numcnt[] 선언
3. 모든 게임에서 유효한 숫자로 선정된 숫자의 개수를 저장하는 변수 cnt 선언
4. 123~987까지 나올 수 있는 모든 숫자를 검사하여 strike, ball 개수가 일치하는지 확인
5. 일치하면 numcnt[해당 숫자]++;
6. numcnt[]값이 N이면 모든 조건을 만족하는 경우이므로 유효한 숫자 개수 하나 증가 cnt++;
7. cnt값 출력

✏️ 정답 코드

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

public class Main {

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

        int N = Integer.parseInt(br.readLine());
        int[] numcnt = new int[1000]; //유효한 숫자로 몇 번 선정되었는지 체크
        int cnt = 0; 

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
            int strike = Integer.parseInt(st.nextToken());
            int ball = Integer.parseInt(st.nextToken());

            int a = num % 10; 
            int b = (num / 10) % 10; 
            int c = (num / 100); 

            for (int k = 123; k <= 987; k++) {
                int strike_ = 0;
                int ball_ = 0;

                int a_ = k % 10; 
                int b_ = (k / 10) % 10; 
                int c_ = (k / 100); 

                // 각 자리가 모두 달라야 유효한 숫자
                if (a_ == b_ || b_ == c_ || c_ == a_ || a_ == 0 || b_ == 0 || c_ == 0) {
                    continue;
                }

                
                if (a == a_) strike_++;
                if (b == b_) strike_++;
                if (c == c_) strike_++;

                
                if (a == b_ || a == c_) ball_++;
                if (b == a_ || b == c_) ball_++;
                if (c == a_ || c == b_) ball_++;

                // 스트라이크와 볼의 조건이 모두 일치하는 경우
                if (strike == strike_ && ball == ball_) {
                    numcnt[k]++;
                }
            }
        }

        //가능한 숫자 개수 확인
        for (int i = 123; i <= 987; i++) {
            int a = i % 10;
            int b = (i / 10) % 10;
            int c = (i / 100);

            // 각 자리가 달라야 유효한 숫자
            if (a == b || b == c || c == a || a == 0 || b == 0 || c == 0) {
                continue;
            }

            if (numcnt[i] == N) {
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}

 

✏️ Note

• 처음부터 아이디어를 떠올리기 어려웠다.
• 브루트 포스로 풀 생각을 못 하고 스트라이크/볼 개수가 어떻게 짝지어질 수 있는지 계속 확인했다.