[백준] 숫자야구 (2503번)

난이도 : Silver 3
Link : https://www.acmicpc.net/problem/2503
Tag : 구현, 브루트포스 알고리즘
풀이일자 : 2024년 9월 18일

📌 문제 탐색하기

N : 질문의 개수
num : 질문한 숫자
strike : 위치,숫자 맞은 개수
ball : 숫자만 맞고 위치는 틀린 숫자 개수

가능한 시간복잡도

정답이 가능한 개수는 1~9까지 숫자로 만들 수 있는 3가지 순열 방식이므로 10P3이 된다. 따라서 경우의 수는 720가지이다.
숫자에 대한 질문을 할때마다 경우의 수는 작아지므로 시간 복잡도 상 문제는 없을것으로 본다.

📌 문제 접근 방법

먼저 가능한 정답을 만들어줄 예정이다.
가능한 정답과 질문한 숫자로 만들 수 있는 숫자의 경우의 수들을 비교해서 strike와 ball 의 개수를 비교하여 실제로 맞을 수 있는 답안을 answer에 업데이트 해줄 예정이다.

📌 코드 설계하기

1. n을 입력받는다.
2. answer을 초기화 한다
   • answer에는 답이 될 수 있는 경우의 수를 저장한다.
   • permutations를 이용하여 1~9까지 숫자로 3개를 골라 만들 수 있는 순열을 배열로 저장한다.
3. n번 만큼 반복하는 for문을 생성한다.
4. num, strike, ball을 입력받는다.
5. correct 배열을 생성한다.
   • correct배열은 정답이 될 수 있는 수를 업데이트 시켜줄 배열이다.
6. 될 수 있는 정답 answer와 질문으로 만들 수 있는 답의 경우의 수 guess를 비교하여 tmp_strike와 tmp_ball을 구한다.
7. tmp_strike와 tmp_ball이 strike와 ball과 같다면 correct 배열에 추가한다.
8. answer배열을 correct배열로 업데이트 하여 될 수 있는 정답을 줄인다.
9. correct배열의 개수를 출력한다.

📌 시도 회차 수정 사항

📌 정답 코드

import itertools

n = int(input())
answer = list(itertools.permutations(list(range(1,10)),3)) #정답 가능한 것

for i in range(n):
    num, strike, ball = map(int, input().split())
    guess = list(map(int,str(num)))

    correct = []
    for k_answer in answer:
        tmp_strike, tmp_ball = 0, 0

        for tmp in range(3):
            if guess[tmp] == k_answer[tmp]: #strike 개수 구하기
                tmp_strike += 1
            if guess[tmp] != k_answer[tmp] and guess[tmp] in k_answer: #ball개수 구하기
                tmp_ball += 1
        if tmp_strike == strike and tmp_ball == ball:
            correct.append(k_answer)
    answer = correct #정답 가능한것 업데이트

print(len(correct))