백준 2503 숫자야구 파이썬 문제풀이 (python 완전탐색)

백준 문제 보러가기

 

백준 2503 숫자야구 파이썬 문제풀이

숫자 야구를 해보신 분들도 있겠지만, 저는 코딩을 통해 처음 알게된 게임이다.

 

서로 다른 숫자 세 자리 수를 생각하고, 이를 물어보면

자리수마다 정답이면 스트라이크, 숫자는 맞으나 위치가 틀리면 볼로 세서 알려준다.

 

324가 정답이라면 

241은 0 스트라이크 2볼이고

924는 2 스트라이크 0볼인 셈이다.

 

질문을 n번 주면 정답으로 나올 수 있는 게 몇 가지인지 출력하면 된다.

 

질문한 숫자에서 스트라이크가 몇 개고, 볼이 몇 개고 하는 것으로 케이스를 나누어 추정하는 방법도 있겠지만,

제한 시간을 먼저 보자. 1초이다.

 

나올 수 있는 전체 가짓수는? 9*8*7 = 504개이다.

질문은 최대 100번 할 수 있으니, 질문 하나에 대해 모든 수를 생각해보면 100 * 504가 되어 50,400 회가 된다.

 

1초에 비하면 그렇게 큰 수는 아니다.

참고로 1초 연산은 반복문으로 계산하면 1억회라고 어림잡으면 된다.

 

그럼 시간에 걸리지는 않으니

모든 수를 대입해서 찾아보는 알고리즘을 짜보자.

 

def Question(question_number, number, s, b):
    strike = 0
    ball = 0
    if question_number // 100 == number // 100:
        strike+=1
    elif str(number).find(str(question_number // 100)) != -1:
        ball += 1
    if (question_number % 100) // 10 == (number % 100) // 10:
        strike+=1
    elif str(number).find(str((question_number % 100) // 10)) != -1:
        ball += 1
    if (question_number % 10) == (number % 10):
        strike+=1
    elif str(number).find(str((question_number % 10))) != -1:
        ball += 1

    if s == strike and b == ball:
        return True
    else:
        return False

n = int(input())
cnt = 0
questionList = []
strikeList = []
ballList = []
for i in range(0,n):
    question, strike, ball = map(int, input().split())
    questionList.append(question)
    strikeList.append(strike)
    ballList.append(ball)

for n1 in range(1,10):
    for n2 in range(1,10):
        for n3 in range(1,10):
            if n1 != n2 and n2 != n3 and n1 != n3:
                number = n1 * 100 + n2 * 10 + n3
                passCnt = 0
                for i in range(0, n):
                    if Question(questionList[i], number, strikeList[i], ballList[i]):
                        passCnt+=1
                if passCnt == 4:
                    cnt+=1
print(cnt)

숫자를 하나하나 잡고, 모든 질문에 부합하는지 확인하면 카운트를 세는 구조이다.

Question이라는 함수를 정의해서 질문한 세 자리 수와 현재 수의 strike와 ball 수가 일치하는지 확인한다.

 

예제를 가지고 테스트 했을 때는 맞게 나오는데 

제출해보니 틀렸다. 문제는 무엇인가.

 

곰곰히 코드를 보고 있다가 passCnt를 상수와 비교하고 있다는 바보같은 실수를 했었다.

 

def Question(question_number, number, s, b):
    strike = 0
    ball = 0
    if question_number // 100 == number // 100:
        strike+=1
    elif str(number).find(str(question_number // 100)) != -1:
        ball += 1
    if (question_number % 100) // 10 == (number % 100) // 10:
        strike+=1
    elif str(number).find(str((question_number % 100) // 10)) != -1:
        ball += 1
    if (question_number % 10) == (number % 10):
        strike+=1
    elif str(number).find(str((question_number % 10))) != -1:
        ball += 1

    if s == strike and b == ball:
        return True
    else:
        return False

n = int(input())
cnt = 0
questionList = []
strikeList = []
ballList = []
for i in range(0,n):
    question, strike, ball = map(int, input().split())
    questionList.append(question)
    strikeList.append(strike)
    ballList.append(ball)

for n1 in range(1,10):
    for n2 in range(1,10):
        for n3 in range(1,10):
            if n1 != n2 and n2 != n3 and n1 != n3:
                number = n1 * 100 + n2 * 10 + n3
                passCnt = 0
                for i in range(0, n):
                    if Question(questionList[i], number, strikeList[i], ballList[i]):
                        passCnt+=1
                if passCnt == n:
                    cnt+=1
print(cnt)

passCnt를 n번으로 바꾸어서 제출하니 

 

성공하였다.

 

내 경우 단순한 반복문으로 접근하였지만,

방법에 따라 중복하지 않는 숫자를 고르는 것이므로 permutation 순열을 이용하는 방법도 있다.

 

다만 python에 익숙하지 않아서 그냥 짰다.