[백준] 2503번: 숫자 야구 (구현, 파이썬)

📌 문제 탐색하기

 영수가 생각하는 숫자의 후보 갯수를 구하는 문제이다. 각 자리에 해당하는 숫자 비교와 1~9의 숫자들 중 숫자를 소거해가며 후보 수를 구할 수 있다. 하나하나 비교해야하므로 구현을 통해 풀 수 있다. 

🔎 문제 조건

• 같은 숫자, 같은 자리면 Strike 1점을 얻을 수 있고, 같은 숫자, 다른 자리면 Ball 1점을 얻을 수 있다. 
• Strike 3점이면 게임은 끝난다. 

🔎  시간 복잡도

• N의 범위 ( 1 ≤ n ≤ 100 )
• 제한 시간: 1초 -> 약 1억번의 연산이 가능하다.
• 100개의 숫자 중 2개를 택해 서로 비교하는 조합의 수는 4950이므로 제한 시간 안에 탐색을 끝낼 수 있다. \
• 스트라이크(S), 볼(B)을 기준으로 정렬하는 데 대략 O(100log100) = 약 664이다. 

🔎 접근 방법 및 알고리즘

• 단순하게 스트라이크가 1이상 인 두 수를 비교하여 공통된 자리, 숫자인 것을 찾는다. 그러면 같은걸 또 반복해서 찾게되는 문제가 발생하므로 가능한 모든 세자리의 조합을 찾고, 이를 입력된 값과 비교하면 되겠다. 
•  

📌 코드 설계하기

1️⃣ 1~9로 만들 수 있는 모든 숫자에 대해 탐색을 진행한다. 순열을 활용한다. 

2️⃣ 만약 num = 124라고 한다면, 입력된 n개의 target에 대해 strike와 ball값을 구한다.

3️⃣위에서 구한 strike, ball 값이 입력된 값과 하나라도 다르다면, 빠져나가서 다른 num에 대해 위의 탐색을 진행한다

4️⃣ 같다면, 가능한 후보숫자를 하나씩 증가 시켜간다.

📌 시도 회차 수정사항

• 아래와 같이 순열을 바로 떠올리지 못해 특징을 찾아보려고 했다..영수가 대답할 스트라이크와 볼의 정수쌍은 다음과 같이 나올 수 있다.
  • 3 스트라이크일 때, 0볼: 게임 종료
  • 2 스트라이크일 때, 0볼
  • 1 스트라이크일 때, 2볼: 후보가 2개로 추려진다.
  • 1 스트라이크일 때, 1볼:
  • 1 스트라이크일 때, 0볼:
  • 0 스트라이크일 때, 3볼: 후보가 2개로 추려진다. (원래 숫자가 abc라 하면, 후보는 cab, bca)
  • 0 스트라이크일 때, 2볼:
  • 0 스트라이크일 때, 1볼:
  • 0 스트라이크일 때, 0볼: 1~9에서 세 자리를 지울 수 있다. 

📌 정답 코드 

import sys
sys.stdin = open('../input.txt')
input = sys.stdin.readline
from itertools import permutations

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9] # 가능한 숫자
ans = 0

for num in permutations(nums, 3):
    isAnswer = True
    for i in range(N):
        if not isAnswer: break
        s, b = 0, 0
        for j in range(3):
            target = str(arr[i][0])
            if int(target[j]) == num[j]:
                s += 1
            elif int(target[j]) in num:
                b += 1
        if s != arr[i][1] or b != arr[i][2]:
            isAnswer = False
            break
    if isAnswer:
        ans += 1
print(ans)