숫자야구 (KOI 본선 2008 초3)

문제

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

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

영수는 민혁이가 말한 수가 몇 스트라이크 몇 볼인지를 답해준다.

  • 민혁이가 영수의 세 자리 수를 정확하게 맞추어 3 스트라이크가 되면 게임이 끝난다. 아니라면 민혁이는 새로운 수를 생각해 다시 영수에게 묻는다.

현재 민혁이와 영수는 게임을 하고 있는 도중에 있다. 민혁이가 영수에게 어떤 수들을 물어보았는지, 그리고 각각의 물음에 영수가 어떤 대답을 했는지가 입력으로 주어진다. 이 입력을 바탕으로 여러분은 영수가 생각하고 있을 가능성이 있는 수가 총 몇 개인지를 알아맞혀야 한다.

아래와 같은 경우를 생각해보자.

민혁: 123 영수: 1 스트라이크 1 볼. 민혁: 356 영수: 1 스트라이크 0 볼. 민혁: 327 영수: 2 스트라이크 0 볼. 민혁: 489 영수: 0 스트라이크 1 볼.

이 때 가능한 답은 324와 328, 이렇게 두 가지이다.

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

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

입력 형식

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

출력 형식

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

입력 예

4 123 1 1 356 1 0 327 2 0 489 0 1

출력 예

2

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

8개의 풀이가 있습니다.

이렇게 찾는게 젤 빠릅니다.

import sys

for i in range(10):

print("%d00" % i)
ball_cnt = input("Ball Count? ")
if ball_cnt[0] == '3':
    print("Strike Out!!!")
    break
elif ball_cnt[0] == '2':
    for j in range(1,10):
        print ("%d%02d" % (i,j))
        ball_cnt = input("Ball Count? ")
        if ball_cnt[0] == '3':
            print("Strike Out!!!")
            sys.exit()
        elif ball_cnt[0] == '2':
            for k in range(1,10):
                print ("%d%d%d" % (i,j,k))
                ball_cnt = input("Ball Count? ")
            if ball_cnt[0] == '3':
                print("Strike Out!!!")
                sys.exit()
elif ball_cnt[0] == '1':
    for j in range(1,10):
        print ("%d%d0" %(i,j))
        ball_cnt = input("Ball Count? ")
        if ball_cnt[0] == '3':
            print("Strike Out!!!")
            sys.exit()
        elif ball_cnt[0] == '2':
            for k in range(1,10):
                print ("%d%d%d" % (i,j,k))
                ball_cnt = input("Ball Count? ")
                if ball_cnt[0] == '3':
                    print("Strike Out!!!")
                    sys.exit()
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
package rootcucu.codefight;
import java.util.*;

// http://codingdojang.com/scode/475
/*
2
1 2 3 1 1
3 5 6 1 0
3 2 7 2 0
4 8 9 0 1
 */
public class Baseball {
    static class Pair {
        Pair(){
            ask = new int[3];
            answer = new int[2];
        }
        int[] ask; 
        int[] answer; //order : S, B
        boolean match(int[] numbers){
            int s = 0, b = 0;
            for (int i = 0; i < 3; i++)
                for (int j = 0; j < 3; j++){
                    if (numbers[i] == ask[j]){
                        if (i == j){
                            s++;
                        }
                        else {
                            b++;
                        }
                    }
                }
            boolean match = s == answer[0] && b == answer[1];
//          System.out.println("ask - " + Arrays.toString(ask) + 
//                  ", answer - " + Arrays.toString(answer) +
//                  ", numbers - " + Arrays.toString(numbers) 
//                  + ", s = " + s + ", b = " + b + ", match = " + match);
            return match;
        }

        @Override
        public String toString() {
            return "Pair [ask=" + Arrays.toString(ask) + ", answer="
                    + Arrays.toString(answer) + "]";
        }
    }

    Pair[] pairs;
    public void getValues(){
        Scanner scanner = new Scanner(System.in);
        System.out.println("how many ask-answers do you have?");
        int n = scanner.nextInt();
        pairs = new Pair[n];
        for (int i = 0; i < n; i++){
            pairs[i] = new Pair();
            Pair pair = pairs[i];
            int[] ask = pair.ask;
            int[] answer = pair.answer;
            System.out.println("Enter ask-answer");
            ask[0] = scanner.nextInt();
            ask[1] = scanner.nextInt();
            ask[2] = scanner.nextInt();
            answer[0] = scanner.nextInt();
            answer[1] = scanner.nextInt();
        }

    }

    public List<int[]> solve(){
        List<int[]> matchNumbers = new ArrayList<>();
        int[] numbers = new int[3];
        for (numbers[0] = 1; numbers[0] < 10; numbers[0]++)
            for (numbers[1] = 1; numbers[1] < 10; numbers[1]++){
                if (numbers[1] == numbers[0])
                    continue;
                for (numbers[2] = 1; numbers[2] < 10; numbers[2]++){
                    if (numbers[2] == numbers[0] || numbers[2] == numbers[1])
                        continue;
                    if (testMatchAll(numbers)){
                        matchNumbers.add(Arrays.copyOf(numbers, 3));
                    }
                }
            }
        return matchNumbers;
    }

    public void printPairs(){
        for (Pair pair:pairs)
            System.out.println(pair);
    }

    private boolean testMatchAll(int[] numbers){
        for (Pair pair:pairs)
            if (!pair.match(numbers))
                return false;
        return true;
    }

    public static void main(String[] args){
        Baseball obj = new Baseball();
        obj.getValues();
        obj.printPairs();
        List<int[]> matchNumbers = obj.solve();
        for (int[] match:matchNumbers){
            System.out.println("match = " + Arrays.toString(match));
        }
        System.out.println("count = " + matchNumbers.size());
    }


}

입력 데이타
4
1 2 3 1 1
3 5 6 1 0
3 2 7 2 0
4 8 9 0 1

아웃풋
Pair [ask=[1, 2, 3], answer=[1, 1]]
Pair [ask=[3, 5, 6], answer=[1, 0]]
Pair [ask=[3, 2, 7], answer=[2, 0]]
Pair [ask=[4, 8, 9], answer=[0, 1]]
match = [3, 2, 4]
match = [3, 2, 8]
count = 2

아오 이렇게 푸는 거였군요 전 뭔 삽질을 한 걸까요. 겨우 세자리면 전부 다 돌려도 얼마 안 되는데 ㅠㅠ - Kim JungRae, 2015/10/06 14:02 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

파이썬 3버전입니다.

import random
numbers = list(range(1,9))              #숫자 1에서9 랜덤배열
random.shuffle(numbers)

sList, answer =[],""
for i in range(3):                      # 3개 고르기
    sList += str(numbers[i])
    answer+= str(numbers[i])

def check(guess):
    strike, ball= 0,0
    li= str(guess); Li= list()
    for i in range(len(li)): 
        Li.append(li[i])           
    for i in range(3):
        if Li[i] == sList[i]:
            strike+=1
        else:
            if Li[i] in sList:
                ball+=1
    print("%d strike %d ball. The answer was %s"%(strike,ball,answer)) # 결과

a = input("guess>")
check(a)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

1~9까지의 3자리 순열을 몽땅 리스트로 만들어서
주어진 데이터로 필터링했습니다.

from itertools import permutations as perm
def umpire(p,r):
    p=str(p);r=str(r)
    s=b=0
    for i in range(len(p)):
        if p[i] == r[i] : s+=1
        elif p[i] in r : b+=1
    return s,b

q = raw_input().split()[1:]
data=[]
while q:
    num,s,b = q.pop(0),int(q.pop(0)),int(q.pop(0))
    data.append((num,s,b))
bucket = [''.join(x) for x in perm('123456789',3)]
for d in data:
    num,s,b = d
    tmp_bucket=[]
    while bucket:
        m = bucket.pop()
        if umpire(m,num) == (s,b) : tmp_bucket.append(m)
    bucket = tmp_bucket

print len(bucket)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#파이썬3.5.1
class Numbase:
    def __init__(self,number=''):
        self.right = str(number)

    def setright(self,n): #생각하는 숫자 세팅
        self.right = str(n)

    def solve(self,n): # 스트라이크와 볼 판별
        Olist = list(self.right) #각 자릿수를 원소로 리스트만들기
        nlist = list(n)          #위와 똑같음
        strike = 0
        ball = 0
        for i in range(len(nlist)):
            if Olist[i] == nlist[i]: #만약 같은 위치에 같은 숫자가 있으면
                strike += 1 #스트라이크 +1
            elif nlist[i] in Olist:  #만약 숫자가 위치에 안맞아도 들어가있으면
                ball += 1 #볼 +1
        return (strike, ball)

    def guess(self,hints): # hints는 각 원소가 '숫자 스트라이크수 볼수'형태인 리스트로 입력받습니다
        numlist = list(filter(lambda x: len(set(x))==3,
                         [str(x) + str(y) + str(z) for x in range(1, 10) for y in range(1, 10) for z in range(1, 10)]))
        correct = [] # numlist; 각 자릿수가 1부터 9까지 3자리의 수중 숫자가 반복되지 않는 수들의 리스트
        for n in numlist: #각 숫자에게 모두
            o = 0 #조건을 충족하는 개수
            for h in hints: #각 힌트마다
                h = h.split()
                if Numbase(n).solve(h[0]) == tuple(map(int,h[1:])): #만약 판별했을 때 스트라이크와 볼이 똑같으면
                    o += 1 # 1더하기
            if o == len(hints): #모든 조건과 충족되면
                correct.append(n) #return할 것에 넣기
        return correct

n = Numbase()
hints = []
for i in range(int(input())):
    hints.append(input())
print(n.guess(hints))
입력:
4
123 1 1
356 1 0
327 2 0
489 0 1
출력:
['324', '328']
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

1~9로 만들 수 있는 세자리 수는 총 9^3 개밖에 없고 또한 각 자릿수가 모든 다른 자릿수인 수들만 고려해주면 되므로 전체탐색으로도 고속으로 해결가능합니다. 아래는 C++ 코드입니다.

#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <algorithm> 
using namespace std; 

int arr[101],s[101],b[101];
int q[3],t[3]; // q: 무작위로 만들어낸 수, t: 물어본 숫자들 int N;

int main(){
int sample,k = 0;
int strike = 0, ball = 0;
int cnt = 0;
scanf("%d",&N);
for (int i = 0; i < N; i++){ // 입력 받기 scanf("%d %d %d",&arr[i],&s[i],&b[i]);
} for (int i = 1; i <= 9; i++){ for (int j = 1; j <= 9; j++){ for (int p = 1; p <= 9; p++){ if (i != j && j != p && p != i){ // 만약 서로 다른 세자리수라면!! q[0] = i; q[1] = j; q[2] = p; for (int a = 0; a < N; a++){ sample = arr[a];
t[0] = sample/100;
sample %= 100;
t[1] = sample/10; t[2] = sample%10;
for (int n = 0; n < 3; n++){ for (int m = 0; m < 3; m++){ if (q[n] == t[m]){ if (n == m) ++strike;
else ++ball;
} } } if (strike == s[a] && ball == b[a]) ++k; strike = 0; ball = 0;
} if (k == N) ++cnt;
k = 0;
} } } } printf("%d\n",cnt);
return 0; }

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

C#으로 작성했습니다. 모든 숫자를 대입시켜 계산했습니다.

using System.Collections.Generic;
using System.Linq;

    public static class Question082CountNumericBaseball
    {

        public static void Answer()
        {
            var inputs = new List<string>();
            inputs.Add("123 1 1");
            inputs.Add("356 1 0");
            inputs.Add("327 2 0");
            inputs.Add("489 0 1");
            var count = CountNumericBaseball(inputs);
        }

        public static int CountNumericBaseball(List<string> inputs)
        {
            var count = 0;
            for (int i = 123; i < 987; i++)
            {
                var curr = i.ToString();
                var total = 0;
                if (curr.Contains("0") || !(curr[0] != curr[1] && curr[1] != curr[2] && curr[0] != curr[2])) continue;
                foreach (var input in inputs)
                {
                    var split = input.Split(' ').ToList();
                    var ball = 0;
                    var strike = 0;
                    var temp = split[0].ToString();
                    for (int j = 0; j < 3; j++)
                    {
                        if (curr[j] == temp[j]) strike++;
                        else if (curr.Contains(temp[j])) ball++;
                    }
                    if (ball == int.Parse(split[2]) && strike == int.Parse(split[1])) total++;
                }
                if (total == 4) 
                    count++;
            }
            return count;
        }

    }
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Ruby

cnt = ->sb,a,b { sb[0]+=1 if a==b; sb[1]+=1 if a[0]==b[0] && a[1]!=b[1]; sb }
valid = ->n1,n2,st,ba do 
  ai, bi = [n1, n2.chars].map {|e| e.map.with_index.to_a }
  ai.product(bi).reduce([0,0]) {|sb,(a,b)| cnt[sb,a,b]} == [st.to_i, ba.to_i]
end

guesses = proc { _,*tail = gets.split; tail.each_slice(3).to_a }
matched = proc {|all,guess| all.select {|e| valid[e, *guess] } }
answers = proc { p guesses[].reduce([*"1".."9"].permutation(3), &matched).size }

Test

$stdin = StringIO.new("4 123 1 1 356 1 0 327 2 0 489 0 1\n")
expect{ answers.() }.to output("2\n").to_stdout

Output

answers.()
4 123 1 1 356 1 0 327 2 0 489 0 1
2
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 8
기 타 x 2
java x 1
python x 3
cs x 1
ruby x 1