백준 2503 - 숫자 야구 (파이썬)
글 작성자: pental
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)
'Programming > 백준' 카테고리의 다른 글
백준 13164 - 행복 유치원 (파이썬) (0) | 2025.03.10 |
---|---|
백준 17951 - 흩날리는 시험지 속에서 내 평점이 느껴진거야 (파이썬) (0) | 2025.03.09 |
백준 17944 - 퐁당퐁당 1 (파이썬) (0) | 2025.03.08 |
백준 17952 - 과제는 끝나지 않아! (파이썬) (0) | 2025.03.07 |
백준 19598 - 최소 회의실 개수 (파이썬) (0) | 2025.03.06 |
댓글
이 글 공유하기
다른 글
-
백준 13164 - 행복 유치원 (파이썬)
백준 13164 - 행복 유치원 (파이썬)
2025.03.10 -
백준 17951 - 흩날리는 시험지 속에서 내 평점이 느껴진거야 (파이썬)
백준 17951 - 흩날리는 시험지 속에서 내 평점이 느껴진거야 (파이썬)
2025.03.09 -
백준 17944 - 퐁당퐁당 1 (파이썬)
백준 17944 - 퐁당퐁당 1 (파이썬)
2025.03.08 -
백준 17952 - 과제는 끝나지 않아! (파이썬)
백준 17952 - 과제는 끝나지 않아! (파이썬)
2025.03.07