본문 바로가기

컴퓨터/BOJ

[BOJ](Python) 2053번 : 숫자 야구

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

 

2503번: 숫자 야구

첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트��

www.acmicpc.net

브루트 포스로 문제를 접근했다.

123부터 987까지 숫자야구에 가능한 숫자를 리스트에 담고, 123 1 1이 주어진다면 리스트에 있는 요소를 123과 비교해보고, 1 스트라이크 1 볼이 아니라면 리스트에서 그 값을 지운다. 이 과정을 반복하고 남은 리스트의 length를 출력하여 값을 확인한다.

 

주어진 코드는 다음과 같다.

arr = []
result = []

for i in range(123, 1000):
    temp = str(i)
    if '0' in temp:
        pass
    elif len(list(set(temp))) == 3:
        arr.append(list(temp))
        result.append(list(temp))
        
for _ in range(int(input())):
    check_number, check_strike, check_ball = map(int, input().split())
    check_number = str(check_number)
    if len(arr) == 1:
        continue
        
    for number in arr:
        strike = 0; ball = 0
        List = list(check_number)
        for i in range(3):
            if number[i] == check_number[i]:
                List.remove(number[i])
                strike += 1
        ball += len(set(List) & set(number))
        
        if check_strike == strike and check_ball == ball:
            continue
        else:
            if number in result:
                result.remove(number)
            else: pass
            
print(len(result))
for i in range(123, 1000):
    temp = str(i)
    if '0' in temp:
        pass
    elif len(list(set(temp))) == 3:
        arr.append(list(temp))
        result.append(list(temp))

숫자야구로 가능한 최소한의 숫자인 123으로 시작한다.

만약에 주어진 숫자에 0이 있다면 패스, set(temp)로 하여서 중복을 제거했을 때 길이가 3이라면 중복이 존재하지 않으므로 temp를 리스트에 추가한다.

 

cf) 나중에 숫자야구에서 불가능한 경우의 수가 있을 때 리스트의 요소를 지워야 하는데, 한 리스트에서 그 값을 지우면서 for loop를 하게 되면 값이 이상해진다.

a = [1,2,3,4,5]
for i in a:
    a.remove(i)
print(a)
>>> [2,4]
    for number in arr:
        strike = 0; ball = 0
        List = list(check_number)
        for i in range(3):
            if number[i] == check_number[i]:
                List.remove(number[i])
                strike += 1
        ball += len(set(List) & set(number))
        
        if check_strike == strike and check_ball == ball:
            continue
        else:
            if number in result:
                result.remove(number)
            else: pass

그다음, 리스트에서 number을 뽑아와서 index가 0일 때, 1일 때, 2일 때 값을 비교해서 같을 때마다 += 1을 하고, 같은 값을 List에서 제외하여 strike였던 수를 제외하고 ball만 비교한다.

 

첫 번째 힌트가 [1,2,3]이고, 브루트 포스로 비교하려는 수가 [1,3,4]라면 number[1] == List[1] 이므로 [1]을 지운다.

그리고 [2,3]의 set인 {2,3}과 [3,4]의 set인 {3,4]를 교집합으로 하여 {3}을 만들고, strike값과, set의 길이가 주어진 ball과 같으므로 지우지 않는다. 

만약 number이 strike와 ball이 다르다면 result.remove(number)하여 결과값에서 제외한다.


다른 풀이:

import sys 
input = sys.stdin.readline

def check(num1, num2, a, b):
	same = [c1 == c2 for c1, c2 in zip(num1, num2)]
	num1 = set(c for i, c in enumerate(num1) if not same[i])
	num2 = set(c for i, c in enumerate(num2) if not same[i])

	return a == sum(same) and b == len(num1 & num2)

candidates = [str(f'{num:03d}') for num in range(1000) if num >= 100]
candidates = [num for num in candidates if '0' not in num]
candidates = [num for num in candidates if len(set(num)) == 3]

for _ in range(int(input())):
	num1, a, b = input().split()
	a, b = int(a), int(b)
	candidates = [num2 for num2 in candidates if check(num1, num2, a, b)]

print(len(candidates))
#출처: ngh3053, https://www.acmicpc.net/source/21926256

candidates를 숫자야구에 가능한 숫자를 가지는 리스트를 만든다.

그 뒤, 브루트포스로 check(비교하려는 대상, 힌트 숫자, strike 수, ball, 수) 함수를 통해 이 함수가 True를 반환하면 후보군에 이 값을 추가, False를 반환하면 후보군을 넣지 않는다.

 

def check(num1, num2, a, b):
	same = [c1 == c2 for c1, c2 in zip(num1, num2)]
	num1 = set(c for i, c in enumerate(num1) if not same[i])
	num2 = set(c for i, c in enumerate(num2) if not same[i])

zip() 내장함수는 iteralble 자료형(ex. string, list,...)들을 tuple로 묶어 object로 반환해주는 함수이다.

zip은 메모리주소만을 참조하고 있으므로 결괏값을 확인하기 위하여 list(zip(num1, num2))이나 tuple(zip(num1, num2))로 자료형을 참조할 수 있도록 하면 된다.

 

#zip() 예시:
num1 = [1,2,3]
num2 = [4,5,6]
print(list(zip(num1, num2)))
>>> [(1, 4), (2, 5), (3, 6)]

그리하여 각각의 tuple == (c1, c2) 에서 c1 == c2이면 strike 이므로 True를 same 리스트에 추가,

같지 않다면 False를 same 리스트에 추가한다.

 

그다음, num1를 집합 자료형으로 초기화시키는데 same [i]가 True 즉, strike였다면 추가시키지 않고, strike가 아니었다면 그 값을 추가시킨다. num2도 num1과 같은 방식으로 만든다.

 

첫 번째 풀이와 마찬가지로 두 자료형을 교집합 하였을 때 ball 과 set의 길이가 같고, strike와 same의 길이가 같다면 True를 반환, 그렇지 않다면 False를 반환한다. 마지막으로 함수의 return이 True라면 num2를 추가시키고 그렇지 않다면 추가하지 않는다. 

 

첫 번째 풀이에 비하여 다음과 같은 장점이 있다.

1. 리스트를 두개 만들지 않고 한 개의 리스트만으로 풀이가 가능.

2. 브루트포스시 123부터 987을 전체 확인했던 것과 다르게 가능하지 않는 경우의 수를 제거하고 다음을 진행하기 때문에 속도가 빠르다.

3. 간결하다.