백준 2503 - 숫자 야구 (파이썬)

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

풀이

• 각 숫자는 1~9까지의 서로 다른 세 자리 수로 이루어진다.
• 상대가 제시한 숫자에 대해 스트라이크(Strike)와 볼(Ball)의 개수를 보고 정답을 유추해야 한다.
  • 스트라이크: 같은 자리에서 같은 숫자가 있을 때 증가.
  • 볼: 다른 자리에 있지만 존재하는 숫자가 있을 때 증가.

브루트포스 알고리즘 이용

• 가능한 모든 세 자리 숫자 조합(순열, permutation) 을 만든다.
• 입력된 모든 질문(qna)과 비교하여 조건을 만족하는 경우만 카운트한다.

count = 0

for permutation in permutations(range(1, 10), 3):
    good = True
    for i in range(len(qna)):
        strike = 0
        ball = 0
        for j in range(3):
            if int(qna[i][0][j]) == permutation[j]:  # 같은 자리 같은 숫자 (스트라이크)
                strike += 1
                continue
            if int(qna[i][0][j]) in permutation:  # 숫자가 있지만 다른 자리 (볼)
                ball += 1

• permutation이 정답 후보인지 확인하기 위해 qna의 모든 질문을 체크한다.
• 스트라이크와 볼 개수를 비교하여 유효한지 판별한다.

시간 복잡도 분석

• 가능한 숫자 조합의 개수: 9P3 = 9! / (9-3)! = 9×8×7 = 504
• 각 조합에 대해 N개의 질문을 검사해야 하므로 O(504 × N) 정도의 시간 복잡도를 가진다.
• N ≤ 100 이므로 최악의 경우 504 × 100 = 약 50,400번 연산 → 충분히 브루트포스 가능!

코드

# 백준 2503 - 숫자 야구
# 분류 : 브루트포스

from itertools import permutations

N = int(input())

qna = []

for _ in range(N) :
    qna.append(input().split())

count = 0
for permutation in permutations(range(1, 10), 3) :
    good = True
    for i in range(len(qna)) :
        strike = 0
        ball = 0
        for j in range(3) :
            if int(qna[i][0][j]) == permutation[j] :
                strike += 1
                continue
            if int(qna[i][0][j]) in permutation :
                ball += 1
        
        if strike != int(qna[i][1]) :
            good = False
        if ball != int(qna[i][2]) :
            good = False

    if good :
        count += 1

print(count)