[알고리즘] 백준 파이썬 2503 숫자 야구

📍 문제 탐색하기

숫자 야구 문제는 숫자 조합을 이용해 가능한 정답 후보를 추려내는 문제이다.
영수가 정한 세 자리 수를 민혁이의 질문과 영수의 답변을 바탕으로 추측한다.

---

문제 조건

1. 영수가 정한 세 자리 수는 1~9의 서로 다른 숫자로 구성된 수이다.
2. 민혁이는 질문한 숫자와 스트라이크/볼 개수를 통해 힌트를 얻는다:
   • 스트라이크: 위치와 숫자가 모두 일치.
   • 볼: 숫자는 일치하지만 위치가 다름.
3. 모든 질문과 답변은 모순이 없도록 주어진다.

---

입력 범위

1. 질문의 개수 N: 1≤N≤100
2. 숫자 조합: 9P3=9×8×7=504개의 후보가 존재.

---

가능한 시간 복잡도

• 각 후보에 대해 N개의 질문을 확인하므로 O(504×N) = 약 50,400 연산으로 해결 가능하다.

---

알고리즘 선택

1. 모든 후보(1~9의 세 자리 수) 생성:
   • 가능한 모든 세 자리 수를 생성한다.
2. 후보 검증:
   • 각 후보를 민혁의 질문과 영수의 답변에 대해 검증한다.
   • 후보가 모든 질문의 조건을 만족하면 유효한 답으로 간주한다.

---

📍 코드 설계하기

1. 입력 받기:
   • 질문의 개수 N과 각 질문의 숫자, 스트라이크, 볼 정보를 입력받는다.
2. 후보 생성:
   • 1부터 9까지의 숫자를 조합해 세 자리 수를 생성한다.
3. 검증 함수 작성:
   • 스트라이크와 볼의 개수를 계산해 주어진 질문의 답변과 일치 여부를 확인한다.
4. 모든 후보를 검증:
   • 각 후보에 대해 모든 질문을 확인하고, 조건을 만족하는 후보를 카운팅한다.
5. 결과 출력:
   • 가능한 답의 총 개수를 출력한다.

---

📍 시도 회차 및 수정 사항

1차 시도 (문제 해결) ✅

import sys
from itertools import permutations
input = sys.stdin.readline

def calculate_score(target, guess):
    strike, ball = 0, 0
    for i in range(3):
        if target[i] == guess[i]:
            strike += 1
        elif guess[i] in target:
            ball += 1
    return strike, ball

n = int(input())
questions = []
for _ in range(n):
    num, s, b = map(int, input().split())
    questions.append((str(num), s, b))

# 가능한 모든 세 자리 수 
candidates = list(permutations('123456789', 3))  

valid_count = 0
for candidate in candidates:
    candidate = ''.join(candidate)  
    is_valid = True
    for question, s, b in questions:
        strike, ball = calculate_score(candidate, question)
        if strike != s or ball != b:
            is_valid = False
            break
    if is_valid:
        valid_count += 1

print(valid_count)

해결 방법

1. itertools.permutations를 이용해 후보를 생성해주었다.
2. 각 후보에 대해 모든 질문의 조건을 확인해주고,
3. 조건을 만족하는 후보만 카운팅하여 출력해주었다.