[TIL] 백준 2503 - 숫자 야구 ( python )

📌 문제 탐색하기

N : 민혁이가 영수에게 질문한 개수

strike : 민혁이가 제시한 수와 영수의 수의 같은 자리에서 숫자가 일치하면 스트라이크

ball: 민혁이가 제시한 수에 포함된 숫자가 영수의 수에 있지만 위치가 다르면 볼

guesses: 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수를 저장하는 배열

 

영수가 마음속으로 생각한 세 자릿수( 1~9, 서로 다른 숫자 )와 민혁이의 질문( 세 자릿수, 스트라이크, 볼 )을 바탕으로 영수가 생각할 수 있는 후보 숫자의 총 개수를 구하는 것이 핵심입니다.

 

1 ≤ N ≤ 100

가능한 시간복잡도

•  후보 수의 총 개수
  • 1부터 9까지 서로 다른 숫자로 구성된 3자리 수의 경우, 총 9 × 8 × 7 = 504가지 후보가 존재합니다.
• 각 후보에 대해 최대 N(최대 100번)의 질문과 비교합니다.
• 각 비교 연산은 상수 시간(3자리 수 비교)이므로, 한 후보 당 O(1)의 시간 소요합니다.
• 총 시간복잡도
  • O(504 × N) = O(50400) → 최악의 경우에도 약 50,000회 연산으로 매우 효율적입니다.

알고리즘 선택

모든 후보를 하나씩 검사하는 브루트포스 방법을 선택합니다.

각 후보에 대해 주어진 모든 질문에 대해 스트라이크와 볼의 계산 결과를 비교함으로써 조건을 만족하는지 확인합니다.

---

📌 코드 설계하기

1. 문제의 Input을 받습니다.
2.  N개의 줄에 대해 '세자리 수, 스트라이크, 볼'을 읽어옵니다.
3. 후보 검증
   1. 후보를 123부터 987까지 순회합니다.
   2. 0이 포함되거나 중복된 숫자가 있는 경우는 제외합니다.
   3. 각 후보에 대해 입력된 모든 질문과 get_strike_ball 함수를 사용해 비교합니다.
   4. 모든 질문을 만족하는 경우 후보의 개수(count)를 증가시킵니다.
4. 스트라이크/볼 계산 함수 (get_strike_ball):
   1. 후보 숫자(candidate)와 질문 숫자(guess)를 전달받습니다.
   2. 두 숫자를 문자열로 변환하여 인덱싱으로 같은 자리에서 숫자가 같은지 확인합니다. → 스트라이크 계산
   3. 후보에 포함된 숫자와 질문에 포함된 숫자를 비교하고, 스트라이크 수를 제외한 나머지를 계산합니다. → 볼 계산
   4. (스트라이크, 볼) 튜플 형식으로 반환합니다.
5. 계산된 후보의 총 개수를 출력합니다.

---

📌 정답 코드

import sys
input = sys.stdin.readline

def get_strike_ball(candidate, guess):
    candidate_str = str(candidate)
    guess_str = str(guess)
    strike = 0
    ball = 0
    
    for i in range(3):
        if candidate_str[i] == guess_str[i]:
            strike += 1
    
    for digit in guess_str:
        if digit in candidate_str:
            ball += 1
    ball -= strike
    return strike, ball


N = int(input())
guesses = []
count = 0

for _ in range(N):
    guess, s, b = map(int, input().split())
    guesses.append((guess, s, b))


for num in range(123, 988): 
    num_str = str(num)
    
    if '0' in num_str or len(set(num_str)) != 3:
            continue  
        
    valid = True

    for guess, s, b in guesses:
        strike, ball = get_strike_ball(num, guess)
        if strike != s or ball != b:
            valid = False
            break
    if valid:
        count += 1

print(count)