[백준 2503번] 숫자야구 with Java

guswls·2024년 5월 4일

백준 브루트포스

알고리즘

목록 보기

14/39

문제

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

코드

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<Query> querys = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int answer = Integer.parseInt(st.nextToken());
			int strike = Integer.parseInt(st.nextToken());
			int ball = Integer.parseInt(st.nextToken());

			querys.add(new Query(answer, strike, ball));
		}

		int result = 0;
		for (int num = 123; num < 988; num++) {
			if (!isValid(num)) {
				continue;
			}

			int correctCount = 0;
			for (Query query : querys) {
				int strikeCount = 0;
				int ballCount = 0;
				String numStr = Integer.toString(query.answer);
				String targetStr = Integer.toString(num);

				// 스트라이크 검사
				for (int i = 0; i < 3; i++) {
					if (numStr.charAt(i) == targetStr.charAt(i)) {
						strikeCount++;
					}
				}

				if (strikeCount != query.strike) {
					break;
				}

				// 볼 검사
				for (int i = 0; i < 3; i++) {
					for (int j = 0; j < 3; j++) {
						if (numStr.charAt(i) == targetStr.charAt(j) && (i != j)) {
							ballCount++;
						}
					}
				}

				if (ballCount != query.ball) {
					break;
				}

				if (strikeCount == query.strike && ballCount == query.ball) {
					correctCount++;
				}
			}

			if (correctCount == N) {
				result++;
			}
		}

		System.out.println(result);
	}

	static boolean isValid(int num) {
		int first = num / 100;
		int second = num % 100 / 10;
		int third = num % 10;

		if (second == 0 || third == 0) {
			return false;
		}

		if (first == second || second == third || first == third) {
			return false;
		}

		return true;
	}

	static class Query {
		int answer;
		int strike;
		int ball;

		Query(int answer, int strike, int ball) {
			this.answer = answer;
			this.strike = strike;
			this.ball = ball;
		}
	}
}

문제 이해

숫자야구 게임이긴 하지만 보통 우리가 생각하는 숫자야구 게임과는 구해야하는 값이 달랐다.
보통의 숫자야구 게임은 스트라이크 또는 볼의 개수로 상대방이 생각한 수를 유추하는 것이 목적이라면, 이 문제는 특이하게 상대방이 생각할 가능성이 있는 수의 개수를 구하는 것이었다.
질문의 개수가 첫 입력으로 주어지고, 그에 이어서 물어본 숫자, 스트라이크의 개수, 볼의 개수가 순차적으로 한 줄에 주어진다.
위 조건에 부합하는 숫자의 개수를 구하는 것이 이번 문제의 답이다.
문제 속 예시를 읽어보면 문제에 대해서는 쉽게 이해할 수 있다.

풀이 방법

문제를 한마디로 요약하면 조건에 부합하는 수의 개수 세기이다.
예를 들어 123, 1, 2라는 입력이 주어졌을 때 123이라는 숫자에 대해서 스트라이크 1개와 볼 2개가 될 수 있는 모든 숫자를 의미한다.
따라서 입력으로 주어지는 질문과 그 답을 Query라는 객체 리스트에 저장한다. 그 후 123 ~ 987에 존재하는 숫자들에 대해서 query를 모두 만족하는 수들을 구한다.
이때 값들은 1) 서로 겹치면 안되며(ex 112) 2) 0이 들어가면 안된다. (120)
만약 위 조건에 만족하는 수라면, 입력받은 쿼리들에 대해서 유효성을 검증한다. 예를 들어 123, 1, 2라는 입력에 대해서 132 라는 값은 1스트라이트 2볼이라는 조건에 부합한다.
strike의 경우는 num.charAt(i)과 target.charAt(i)가 만족하는 경우를 의미한다.
ball의 경우는 수가 안에 존재하지만, 자리는 다른 경우를 의미한다. 따라서 이중for문을 사용하며 num.charAt(i) == target.charAt(j)이면서 i != j인 경우가를 의미한다.
이렇게 해서 어떤 숫자가 모든 쿼리들에 대해서 만족한다면, result를 1증가시킨다.

핵심 포인트

for문의 범위, 유효 범위에 대해서 신경써야 한다.
987도 범위에 포함되어야 하기 때문에 988까지로 잡아야 한다.
그리고 0에 대해서도 체크를 해주어야 한다.
입력을 모두 받은 후에 for문을 순회하며 입력 조건에 맞는 수들을 구해야 한다. 물론 소거법으로도 해결할 수 있을지도 모르겠으나, 너무 복잡해진다. 이번 문제의 경우는 브루트포스로도 충분히 선형의 시간복잡도로 해결할 수 있다.