[class2]백준 2503번(숫자 야구) - 코테공부 25일차(2025.02.16)

문제유형

브루드 포스 알고리즘

풀이 방법 도출 과정

1. 영수, 민혁이 1~9까지 3개를 마음속으로 생각한다. 

2. 민혁이는 그 3개를 말한다. 만약 하나가 영수의 세자리수의 동일한 자리에 위치하면 스트라이크

3. 숫자가 영수의 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼

4. 몇 스트라이크 몇 볼이라고 영수는 말해준다.

5. 입력을 바탕으로 영수가 생각하고 있을 가능성이 있는 수가 총 몇 개인지를 알아맞춰야한다.

6. 물어보는 수는 최대 100개이므로 모든 경우의 수에서 삭제하는 방법으로 브로트 포스 알고리즘을 사용하는 풀이를 사용해보도록 하겠다.

시간 복잡도

최악의 경우 100 X 10P3 =  7200 이다.  그러므로 시간복잡도 측면에서 문제될 것은 없다. 

코드 및 간단설명

브루트포스 알고리즘을 사용해보았다. 

from itertools import permutations

n = int(input())
infos = [input().split() for _ in range(n)]
ans = 0

for cur in permutations(range(1, 10), 3):
    ok = True
    
    for num, st, bl in infos:
        cur_st = cur_bl = 0
        
        for i in range(3):
            if str(cur[i]) == num[i]:
                cur_st += 1
            elif str(cur[i]) in num:
                cur_bl += 1
     
        if cur_st != int(st) or cur_bl != int(bl):
            ok = False
            break
    
    if ok:
        ans += 1
        
print(ans)

다른 풀이

1) 브루트 포스 다른 사용

이 문제는 힌트의 스트라이크와 볼 수를 만족하지 않는 숫자들을 필터링하여 제거하는 방식이다. 이 경우 반복횟수가 이전의 풀이보다 훨씬 더 효과적으로 할 수 있다. 

def count_strike_ball(candidate, guess):
    # 각 자리별로 스트라이크 계산
    strike = sum(c == g for c, g in zip(candidate, guess))
    # 전체 공이 일치하는 횟수에서 스트라이크 수를 빼서 볼 계산
    ball = sum(g in candidate for g in guess) - strike
    return strike, ball

# 1부터 9까지의 숫자로 이루어진 3자리 서로 다른 숫자 후보 집합 생성
candidates = [str(a) + str(b) + str(c) 
              for a in range(1, 10) 
              for b in range(1, 10) 
              for c in range(1, 10) 
              if a != b and b != c and a != c]

n = int(input())
infos = [input().split() for _ in range(n)]

# 각 힌트에 대해 후보 집합 필터링
for num, s, b in infos:
    s, b = int(s), int(b)
    candidates = [cand for cand in candidates if count_strike_ball(cand, num) == (s, b)]

print(len(candidates))