[백준][파이썬] 2503번

문제

정보문화진흥원 정보 영재 동아리에서 동아리 활동을 하던 영수와 민혁이는 쉬는 시간을 틈타 숫자야구 게임을 하기로 했다.

• 영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324)
• 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 영수에게 묻는다. (예: 123)
• 민혁이가 말한 세 자리 수에 있는 숫자들 중 하나가 영수의 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번으로 센다. 숫자가 영수의 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼 한 번으로 센다.

영수는 동아리의 규율을 잘 따르는 착한 아이라 민혁이의 물음에 곧이곧대로 정직하게 답한다. 그러므로 영수의 답들에는 모순이 없다.

민혁이의 물음들과 각각의 물음에 대한 영수의 답이 입력으로 주어질 때 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수, 이렇게 총 세 개의 정수가 빈칸을 사이에 두고 주어진다.

출력

첫 줄에 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력한다.

링크

2503번: 숫자 야구 (acmicpc.net)

2503번: 숫자 야구

 

 접근 방법

1. 만들 수 있는 모든 숫자의 조합(num)을 생각하고.
2. 민혁이가 말한 조합(t)에 대한 영수의 응답(s,b)을 바탕으로 세트에서 오답을 제거한다.
   1. t와 num을 비교해 볼과 스트라이크 수(s_cnt,b_cnt)를 센다
   2. 볼과 스트라이크 수(s_cnt,b_cnt)가 영수의 응답(s,b)와 같지 않으면 num에서 제거한다.
   3. 이를 모든 num의 요소에 대해 반복한다.
3. 정답만 남아 있는 num 리스트의 길이를 출력한다.

완전 탐색 참고 자료 : [알고리즘][파이썬] Exhaustive Search / 완전 탐색 — y-seo의 딩코 기록들 (tistory.com)

[알고리즘][파이썬] Exhaustive Search / 완전 탐색

 

 풀이

1. 순열(permutation) 함수

Python의 모듈 itertools로 순열을 쉽게 만들어준다. itertools란 반복자를 만드는 모듈이다. 따라서 아래와 같이 package import가 필요하다.

import itertools

순열이란 서로다른 n개에서 r개를 선택할 때 순서를 고려하여 중복없이 뽑는 경우이다. 사용 방법은 아래와 같다.

조건 

from itertools import permutations

형식 : 객체(리스트/튜플/문자열) 안에서 r을 선택하는 형식으로 작동

permutations(객체, r)

 

리턴값 : 순열 경우의 결과를 튜플 형식

2. Type Error

이 부분은 아래 코드를 먼저 확인하고 "왜 자료형을 저렇게 하지" 싶은 의문점이 들면 읽어 보길 추천합니다.. 

처음 민혁이가 말하는 조합을 변수 t로 받아왔다. 이때는 map 함수를 통해 받아왔다. 우리는 t를 인덱스로 접근하여 num의 요소와 비교를 하여야 하는데.. map 함수를 이용하면 인덱스로는 접근이 불가하다. 슬라이싱 또한 불가하다. 따라서 인덱스 사용이 가능한 list 자료형으로 바꿔 주어야 한다. 

list() 함수를 사용할 때는 인자로 반복할 수 있는 객체가 와야 한다. 따라서 문자열, 튜플, 집합이 가능한데 우리가 map 함수에서 int형으로 받았기 때문에 바로 list(t) 하여 함수를 사용하는 것은 불가능하다. 따라서 str 자료형으로 한 번 더 바꿔주고 list() 함수를 사용하여야 한다.

하지만 또 이후에 직접 비교해줄 때는 int 자료형으로 비교해야 하기 때문에 int(t[i]) 처럼 인덱스로 접근하고 int 자료형으로 바꿔주어야 한다.  

 

 전체코드

import sys
from itertools import permutations

n = int(input())
num = list(permutations([1,2,3,4,5,6,7,8,9], 3))

for i in range(n):
    t, s, b = map(int, input().split()) #맞추는 사람
    t = list(str(t)) #인덱스 접근을 위해
    remove_cnt = 0 

    for j in range(len(num)):
        s_cnt = b_cnt = 0
        j -= remove_cnt #삭제된 조합만큼 스킵
        
        for k in range(3): #비교하기
            if int(t[k]) in num[j]: 
                if k == num[j].index(int(t[k])): #스트라이크
                    s_cnt += 1
                else: #볼
                    b_cnt += 1
        
        if s_cnt != s or b_cnt != b: #틀린 정답
            num.remove(num[j])
            remove_cnt += 1

print(len(num))