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

숨·2024년 9월 18일

코테

알고리즘 문제 풀이

목록 보기

78/105

📌 문제 : 백준 2503번

📌 문제 탐색하기

N : 질문 횟수 $(1 ≤ N ≤ 100)$

숫자 야구 게임에서 질문한 세 자리 수, 스트라이크 개수, 볼 개수를 통해 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력하는 문제이다.

문제 풀이

⭐️ 숫자 야구 규칙

영수가 1 ~ 9 사이의 서로 다른 숫자로 구성된 세 자리 수 생각

민혁 → 영수에게 세 자리수 맞는지 질문

스트라이크 : 세 자리 수 중 영수의 숫자와 동일한 자리에 위치한 경우

볼 : 세 자리 수 중 영수의 숫자에 있지만 위치가 다른 경우

이 문제는 1 ~ 9 사이의 서로 다른 숫자로 구성된 세 자리 수를 모두 만들어내서 민혁이의 질문에 대한 결과를 활용해 스트라이크와 볼 조건에 만족하는 경우만 세는 식으로 구현한다.

from itertools import permutations를 활용해 9개의 숫자 중 서로 다른 3개를 골라서 세 자리 수를 만들어 저장한다.

민혁이의 질문, 스트라이크 수, 볼 수도 리스트에 저장한다.

만든 세 자리 수 숫자를 하나씩 민혁이 질문에 대한 결과와 비교하면서 스트라이크 수, 볼 수를 계산한다.

해당 숫자가 유효한지 아닌지를 나타내는 플래그 정의
- 정답이 될 수 없다면 다음 질문으로 넘어가도록 종료 조건 추가
민혁이가 제시한 숫자를 만든 세 자리 수와 비교하기 위해 문자열로 변환
- 질문과 한 자리씩 비교해 스트라이크, 볼 계산
- 계산 결과가 질문 결과와 일치하는지 확인
조건에 만족하면 답 개수 증가

가능한 시간복잡도

9개 숫자 중 서로 다른 숫자 3개 선택 → $O(504)$
질문 반복 → $O(N)$

최종 시간복잡도
$O(504 * N)$ 로 최악의 경우 $O(50400)$ 이 되는데 이는 1초 내에 연산 가능하다.

알고리즘 선택

세 자리 수 만들고 하나씩 질문 결과와 비교하며 스트라이크, 볼 계산해 가능성 있는지 확인하기

📌 코드 설계하기

필요한 입력 받기
답 개수 저장할 변수 정의
세 자리 수 만들기
세 자리 수와 입력받은 질문 결과를 비교해 정답 가능성 있는 숫자 확인
결과 출력

📌 시도 회차 수정 사항

1회차

정답이 계속 0이 나왔다.
만든 세 자리수의 각 숫자는 정수이고, 민혁이의 질문 숫자는 문자열로 변환해서 자료형이 안맞기 때문에 같은지 확인할 수 없는 문제가 나타났다.
list(map(int, str(question[0]))) 로 문자열 형식으로 바꾼 후 map함수로 각 자리 숫자를 정수형으로 변환해 리스트에 넣는 식으로 변경하여 원하는 결과를 얻을 수 있었다.

📌 정답 코드

import sys
from itertools import permutations

input = sys.stdin.readline

# N 입력
N = int(input())

# 민혁의 숫자, 스트라이크 수, 볼 수 입력
questions = [list(map(int, input().split())) for _ in range(N)]

# 답 개수 변수 정의
count = 0

# 1~9 중 서로 다른 3개 골라 세 자리 수
nums = list(permutations(range(1, 10), 3))

# 답 확인
for num in nums:
    # 정답 가능성 있는지 나타내는 플래그 변수
    valid = True

    for question in questions:
        question_num = list(map(int, str(question[0])))
        answer_strikes, answer_balls = question[1], question[2]

        # 스트라이크 수, 볼 수 초기화
        strikes = balls = 0

        # 계산
        for i in range(3):
            # 같은 자리 같은 숫자
            if num[i] == question_num[i]:
                strikes += 1
            # 다른 자리 같은 숫자
            elif num[i] in question_num:
                balls += 1

        # 유효한지 아닌지 확인
        if answer_strikes != strikes or answer_balls != balls:
            valid = False
            break

    # 모든 조건 만족하면 정답 가능성 있는 답 수 증가
    if valid:
        count += 1

# 결과 출력
print(count)