[백준 2503] 숫자야구 (자바)

백준 2503번: 숫자야구

문제 설명

숫자야구 게임은 상대방의 숫자를 맞추는 게임입니다. 상대방은 1부터 9까지 서로 다른 세 숫자를 정하고, 우리는 그 숫자를 맞추기 위해 시도합니다. 각 시도마다 다음과 같은 정보를 받습니다:

• 스트라이크: 자리와 숫자가 모두 맞는 경우
• 볼: 숫자는 맞지만 자리가 틀린 경우

주어진 시도와 결과를 바탕으로 가능한 모든 경우의 수를 계산하는 문제입니다.

문제 접근 방법

1. 1부터 9까지의 숫자 중 세 개를 중복 없이 선택합니다.
2. 각 선택된 숫자가 주어진 조건을 만족하는지 확인합니다.
3. 모든 조건을 만족하는 숫자 조합의 수를 계산합니다.

시간 복잡도 분석

O(N * 504)

이 문제는 1부터 9까지의 숫자 중 세 개를 중복 없이 선택하는 모든 경우를 확인해야 합니다. 따라서 가능한 조합의 수는 9P3 = 9 * 8 * 7 = 504입니다. 각 조합마다 N개의 시도를 검증해야 하므로 전체 시간 복잡도는 O(N * 504)입니다. 이 정도의 시간 복잡도는 일반적인 입력 크기에서 충분히 처리할 수 있습니다.

해결 방법

아래는 주어진 조건을 만족하는 숫자 조합의 수를 계산하는 Java 코드입니다:

package re_01;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_2503_숫자야구_2트 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Integer N = Integer.parseInt(br.readLine());
        List<int[]> answers = new ArrayList<>();
        List<String[]> guess = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String[] str = st.nextToken().split("");
            guess.add(str);
            answers.add(new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
        }
        int answer = 0;
        for (int x = 1; x <= 9; x++) {
            for (int y = 1; y <= 9; y++) {
                for (int z = 1; z <= 9; z++) {
                    if (x != y && y != z && z != x) {

                        int count = 0;
                        for (int i = 0; i < N; i++) {
                            int exStrike = answers.get(i)[0];
                            int exBall = answers.get(i)[1];

                            int ball = 0;
                            int strike = 0;

                            int i1 = Integer.parseInt(guess.get(i)[0]);
                            int i2 = Integer.parseInt(guess.get(i)[1]);
                            int i3 = Integer.parseInt(guess.get(i)[2]);

                            // xyz <- 정답이라 생각되는 수
                            if (i1 == x) {
                                strike++;
                            } else if (i1 == y) {
                                ball++;
                            } else if (i1 == z) {
                                ball++;
                            }
                            //
                            if (i2 == x) {
                                ball++;
                            } else if (i2 == y) {
                                strike++;
                            } else if (i2 == z) {
                                ball++;
                            }
                            //
                            if (i3 == x) {
                                ball++;
                            } else if (i3 == y) {
                                ball++;
                            } else if (i3 == z) {
                                strike++;
                            }

                            if (strike == exStrike && ball == exBall) {
                                count++;
                            }
                        }
                        if (count == N) {
                            System.out.println(String.format("%d %d %d", x, y, z));
                            answer++;
                        }
                    }
                }
            }
        }
        System.out.println(answer);
    }
}