[백준] 2503번: 숫자 야구 - 파이썬/python

https://www.acmicpc.net/problem/2503

2503번: 숫자 야구

접근 방식

- 하나의 질문/대답 정보를 통해 유추할 수 있는 숫자들의 풀을 차례로 조사하여 교집합 처리해주는 방식

- or 가능한 전체 경우의 수에서 하나의 질문/대답 정보를 통해 불가능한 숫자를 차례로 제외해주는 방식

 

코드 풀이

위의 접근방식 중 첫 번째 방식은 하나의 질문/대답에서 고려해야 하는 순열, 조합의 경우의 수가 너무 복잡하여 두 번째 방식을 활용하였습니다. 두 번째 방식은 차례대로 탐색 대상의 수를 줄여가므로 소요 시간도 적을 것이라고 생각했습니다.

from itertools import permutations

num = list(range(1, 10)) # 1, 2, ... 8, 9
num_pool = [] # 123, 124, 125 ... 789 (9*8*7 = 504개) 가 튜플 형태로 저장
for i in permutations(num, 3):
    num_pool.append(i)

n = int(input()) # 질문/대답의 수

for _ in range(n):
    checking, ans_st, ans_b = map(int, input().split())
    poss = [] # 하나의 질문/대답에서 유추된 가능성이 있는 수

    for num_check in num_pool: # 현재 가능성이 있는 수를 하나씩 조사
        strike, ball = 0, 0
        for i, check in enumerate(str(checking)):
            if int(check) == num_check[i]:
                strike += 1
            if int(check) != num_check[i] and int(check) in num_check:
                ball += 1

        if strike == ans_st and ball == ans_b: # 질문한 숫자와 동일한 대답이 얻어지는 경우
            poss.append(num_check)
    num_pool = poss # 다음 질문/대답은 현재의 질문/대답에서 유추된 가능성이 있는 수 중에서 유추
    
print(len(poss))

코드는 먼저 123 부터 789까지 고려 대상인 숫자 풀을 만들어 num_pool 리스트에 저장하는 것으로 시작합니다. 어차피 자리수별로 탐색하며 strike, ball 여부를 판단해야 하므로 튜플 형태로 그대로 리스트에 저장했으며, 1부터 9까지의 수 중에서 세 가지 순열로 숫자를 뽑는 permutations 함수를 활용했습니다.

만들어진 num_pool 리스트 내의 숫자를 for loop로 하나씩 탐색하며 주어진 숫자(checking)를 질문했을 때 strike 값과 ball 값이 대답(ans_st, ans_b)과 동일하게 나오는지 확인했습니다. 동일하게 나오는 경우 정답일 가능성이 있는 수로 poss 리스트에 따로 저장했습니다.

질문은 n번 반복되므로 다음 질문으로 넘어갈 때마다 탐색 대상인 num_pool 리스트를 poss로 업데이트 했습니다. 직전 질문에서 정답으로 추정되는 수만을 탐색해야 차례로 불가능한 숫자를 제외해주는 효과가 나기 때문입니다. 

 

메모

for loop를 돌고있는 리스트의 원소를 직접 제거하게 된다면, 순서를 건너뛰게 되므로 오류의 원인이 됩니다.

예를 들어 다음과 같은 경우에서, example 리스트에서 3을 발견해 삭제한 후 4가 아닌 5를 탐색하게 되므로 print(i)의 출력은 1 2 3 5가 됩니다. 누락의 원인은 for loop는 인덱스를 통해 리스트에 접근하기 때문으로 추정됩니다.

example = [1,2,3,4,5]

for i in example:
    print(i)
    if i == 3:
        example.remove(3)