코딩 챌린지 10일차 : 2503번 숫자 야구(S3)

2503 : 숫자 야구 - 문제 링크

1. 문제 탐색하기

입력

n 질문의 수
guess 추측한 세 자리 수
strike 스트라이크 개수
ball 볼 개수

구하고자 하는 것

추측이 모두 끝난 후 가능한 답의 총 개수
len(숫자 후보군)

알고리즘 설계

n번의 추측에 걸쳐 후보군이 점점 사라지므로
123 ~ 987의 수 리스트를 만들어 놓고 지워나가야 한다.

0을 제외하고, 자리마다 중복이 있으면 안되니
삼중 for문을 적절하게 사용하여 nums를 만든다.

그리고 nums의 모든 수(num)에 대해
num이 답이라고 가정했을 때의 스트라이크, 볼 개수를 계산하여
실제 스트라이크, 볼 개수와 맞지 않으면 해당 수를 후보군에서 지운다.

시간복잡도

명령어 수에 대해, nums의 모든 수에 대해 체크, 수의 각 자리마다 체크
-> n 최대 504 3 -> $O(n)$
1 $\leq$ n $\leq$ 100 이므로 시간 내에 통과 가능

2. 코드 설계하기

1. 숫자 리스트 생성
2. input 받기
3. 후보군의 모든 수에 대해 가능 여부 확인
• 각 자리마다 스트라이크, 볼 체크하여 개수++

3. 시도 회차 수정 사항

1회차) 성...공...

4. 정답 코드

import sys
input = sys.stdin.readline

nums = []

# 숫자 리스트 생성
for i in range(1, 10):
    for j in range(1, 10):
        for k in range(1, 10):
            if i != j and j != k and k != i:
                nums.append(str(i) + str(j) + str(k))

# input 받기
n = int(input())
for _ in range(n):
    guess, strike, ball = input().split()
    strike, ball = int(strike), int(ball)
    
    delete = []

    # nums의 모든 수에 대해 가능 여부 확인
    for num in nums:
        s, b = 0, 0
        # 각 자리마다 확인
        for i in range(3):
            if num[i] in guess:
                if num[i] == guess[i]:  s += 1
                else:                   b += 1
        if s != strike or b != ball:    delete.append(num)
    for d in delete: nums.remove(d)

print(len(nums))

삽질을 정말... 많이 했다. 처음에는 s,b에 대한 모든 케이스를 나누어 생각하다가 반대로 nums에 초점을 맞추니 해결되었다. 구현 재밌는데 어려워ㅠㅠ

5. 해설지 참고 후

• 순열 만들어야 할 때는 permutation 라이브러리 사용