[백준] 2503번 숫자 야구
- 알고리즘/백준
- 2020. 6. 12. 17:22
문제
정보문화진흥원 정보 영재 동아리에서 동아리 활동을 하던 영수와 민혁이는 쉬는 시간을 틈타 숫자야구 게임을 하기로 했다.
- 영수는 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개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수, 이렇게 총 세 개의 정수가 빈칸을 사이에 두고 주어진다.
출력
첫 줄에 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력한다.
이 문제는 역으로 생각해되는 문제다.
원래 숫자야구는 사용자가 번호를 입력하면 그것에 맞게 컴퓨터가 스트라이크, 볼을 알려주는 시스템이다.
근데 여기에서는 사용자가 어떤 번호를 입력하는지.. 스트라이크, 볼에 대한 정보를 알려준다.
그러니까 컴퓨터가 어떤 번호로 스트라이크, 볼인지는 알려주지 않는 다는 이야기다.
어떻게든, 스트라이크. 볼에 맞는 숫자를 찾아야한다.
이 문제 같은 경우는 하드코딩을 했다.ㅜㅜ
package _2020_06_12.A;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
class Base {
int strike;
int ball;
public Base() {}
Base(int strike, int ball) {
this.strike = strike;
this.ball = ball;
}
}
public class Main {
static int[] number = new int[10];
static boolean[] can = new boolean[10];
static List<String> baseball = new ArrayList<>();
static void go(int index) {
if (index == 3) {
String result = "";
for(int i = 0;i<3;i++) {
result+=number[i]+"";
}
baseball.add(result);
return;
}
for (int i = 1; i <= 9; i++) {
can[i] = true;
number[index] = i;
go(index+1);
can[i] = false;
}
}
static Base collect(String result,String call) {
int strike = 0;
int ball = 0;
if(result.charAt(0) == call.charAt(0)) {
strike++;
}
if(result.charAt(1) == call.charAt(1)) {
strike++;
}
if(result.charAt(2) == call.charAt(2)) {
strike++;
}
if(result.charAt(0) == call.charAt(1)) {
ball++;
}
if(result.charAt(0) == call.charAt(2)) {
ball++;
}
if(result.charAt(1) == call.charAt(2)) {
ball++;
}
if(result.charAt(1) == call.charAt(0)) {
ball++;
}
if(result.charAt(2) == call.charAt(1)) {
ball++;
}
if(result.charAt(2) == call.charAt(0)) {
ball++;
}
return new Base(strike,ball);
}
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int temps = n;
List<String> finsh = new ArrayList<>();
go(0);
while(n-- > 0) {
String call = sc.next();
int strike = sc.nextInt();
int ball = sc.nextInt();
for (String t : baseball) {
Base base = collect(t, call);
if (base.strike == strike && base.ball == ball) {
finsh.add(t);
}
}
}
int lastG = 0;
for(int i = 0; i<finsh.size();i++) {
int cnt = 1;
for(int j = i+1;j < finsh.size();j++) {
if (finsh.get(i).equals(finsh.get(j))) {
cnt++;
}
}
if (temps == cnt) {
lastG++;
}
}
System.out.println(lastG);
}
}
코딩하고 보니 100줄이 넘는 코드가 되있었다.ㅜㅜ
일단 메서드 별로 살펴보면
go, collect메소드가 있다.
go같은 경우는 컴퓨터가 어떤 번호로 작성했는지 미리 예상해서 등록하는 메서드다.
원래는 리턴값을 사용해서 하려고 했지만... 리턴 값을 이용하게 되면 값이 하나만 등록 되기 때문에 어쩔 수 없이 List에다 저장 시켰다. 그리고 굳이 메소드 안에 있을 이유가 없기 때문에 맴버변수로 분리시켰다.
그 다음 메소드는 collect인데 이게 원래 이렇게 작성하면 안된다.
반복문으로 작성해야하는데 그걸 까먹어서...
그냥 if문 도배로 그 문제를 해결했다.
리턴 값이 Base인데 Base인 이유는 2가지의 값을 동시에 리턴을 시켜주고 싶기 때문이다. 클래스또는 struct를 묶어서 사용하면 동시에 2가지이상을 리턴 시키는 효과를 보여준다.
그러면 strike와 ball의 갯수가 나온다. 그리고 우리가 알고 있는 스트라이크 , 볼의 값과 비교해본다.
그러면 뭔지는 모르지만 같은 번호가 나온다.
이들을 다시 저장시킨다.
그리고 for문 2개를 사용해서 확인해준다.
포문 2개를 사용하게 되면 쓸모없는 계산이 되는 약점이 존재하긴 하지만...
구현하기에는 느린 방법이 아니라 생각한다. 그래서 이렇게 하였다.
그러면 값이 나오는데... 원래 우리가 구하려는 값을 미리 등록해두었다.
그 값이랑 증가값을 비교해보면 같은 값이 n개 나오는데
그게 답이다.
나는 이렇게 끔찍하게 풀었다.
일단은 풀어서 다행이긴 한데. 너무 더럽다.
이 문제에서 중요한게 있는데 111, 112같은 숫자들은 등록이 되면 안된다.
import java.util.Scanner;
public class Main {
static int N;
static int[][] input;
public static void main(String[] args) {
getInput();
System.out.println(playGame());
}
public static void getInput() {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
input = new int[N][5];
for(int i = 0; i < N; i++) {
int guess = sc.nextInt();
int strike = sc.nextInt();
int ball = sc.nextInt();
input[i][0] = guess / 100;
input[i][1] = (guess - (input[i][0] * 100)) / 10;
input[i][2] = (guess - (input[i][0] * 100)) - (input[i][1] * 10);
input[i][3] = strike;
input[i][4] = ball;
}
}
public static int playGame() {
int rslt = 0;
for(int i = 1; i <= 9; i++) {
for(int j = 1; j <= 9; j++) {
if(i==j) continue;
for(int k = 1; k <= 9; k++) {
if(i==k) continue;
if(j==k) continue;
boolean possibleYn = true;
for(int l = 0; l < N; l++) {
int strike = 0;
int ball = 0;
// 첫번째 자리 체크
if(i == input[l][0]) {
strike++;
}else if(i==input[l][1] || i==input[l][2]) {
ball++;
}
// 두번째 자리 체크
if(j == input[l][1]) {
strike++;
}else if(j==input[l][0] || j==input[l][2]) {
ball++;
}
// 세번째 자리 체크
if(k == input[l][2]) {
strike++;
}else if(k==input[l][0] || k==input[l][1]) {
ball++;
}
if(strike != input[l][3] || ball != input[l][4]) {
possibleYn = false;
break;
}
}
if(possibleYn) {
rslt++;
}
}
}
}
return rslt;
}
}'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 11729번 하노이 탑 이동 순서 (0) | 2020.06.16 |
|---|---|
| [백준] 17219번 비밀번호 찾기 (0) | 2020.06.14 |
| [백준] 1202번 보석 도둑 (0) | 2020.06.11 |
| [백준] 2012번 등수 매기기 (0) | 2020.06.11 |
| [백준] 2812번 크게 만들기 (0) | 2020.06.10 |