[프로그래머스 알고리즘] 2단계 숫자야구 -완전탐색

프로그래머스 2단계 숫자야구 문제

 url : https://programmers.co.kr/learn/courses/30/lessons/42584?language=java

문제설명

숫자 야구 게임이란 2명이 서로가 생각한 숫자를 맞추는 게임입니다. 각자 서로 다른 1~9까지 3자리 임의의 숫자를 정한 뒤 서로에게 3자리의 숫자를 

불러서 결과를 확인합니다. 그리고 그 결과를 토대로 상대가 정한 숫자를 예상한 뒤 맞힙니다. 

 * 숫자는 맞지만, 위치가 틀렸을 때는 볼

 * 숫자와 위치가 모두 맞을 때는 스트라이크

예를 들어, 아래의 경우가 있으면

A : 123

B : 1스트라이크 1볼.

A : 356

B : 1스트라이크 0볼.

A : 327

B : 2스트라이크 0볼.

A : 489

B : 0스트라이크 1볼.

이때 가능한 답은 324와 328 두 가지입니다.

제한사항

질문의 수는 1 이상 100 이하의 자연수입니다.baseball의 각 행은 [세 자리의 수, 스트라이크의 수, 볼의 수] 를 담고 있습니다.

입출력 예

baseball	return
[[123, 1, 1], [356, 1, 0], [327, 2, 0], [489, 0, 1]]	2

자바코드

            
import java.util.*;
class Solution {
    public static int solution(int[][] baseball) {
        Stack stack = new Stack<>();
        for(int i = 1; i < 10; i++) {
        	for(int j = 1; j < 10; j++) {
        		for(int k = 1; k < 10; k++) {
        			if(i != j && j != k && i != k) {
        				stack.add(String.valueOf(i * 100 + j * 10 + k));
        			}
        		}
        	}
        }
        Stack temp = new Stack<>();
        boolean flag = true;
        while(!stack.isEmpty()) {
        	String num = stack.pop();
        	for(int i = 0; i < baseball.length && flag; i++) {
        		int strike = strike(num, String.valueOf(baseball[i][0]));
        		int ball = ball(num, String.valueOf(baseball[i][0])) - strike;
        		if(strike != baseball[i][1] || ball != baseball[i][2]) {
        			flag = false;
        		}
        	}
        	if(flag) {
        		temp.add(num);
        	}
        	flag = true;
        }
        return temp.size();
    }
	
	public static int strike(String num, String target) {
		int cnt = 0;
		for(int i = 0; i < target.length(); i++) {
			cnt = num.charAt(i) == target.charAt(i) ? cnt + 1 : cnt;
		}
		return cnt;
	}
	
	public static int ball(String num, String target) {
		int cnt = 0;
		for(int i = 0; i < target.length(); i++) {
			cnt = num.contains(String.valueOf(target.charAt(i))) ? cnt + 1 : cnt;
		}
		return cnt;
	}
}

문제설명

야구게임은 서로 다른 세개의 숫자를 이용해서 하는 게임이기 때문에 게임에서 사용하는 문자열 패턴은 1000개 이하이므로, 완전탐색으로 풀이 가능하다.

먼저 스택에 게임에서 사용하는 세자리 숫자들을 모두 추가했다. 단, 서로 다른 세개의 숫자만 넣을 수 있도록 조건문을 추가했다.

그리고 다른 스택에는 조건에 맞는 정답에 해당되는 숫자만을 저장하기 위해 생성했다. 마지막으로 스택에 있는 모든 숫자들이 조건에 맞는지 확인한다.

여기서 ball의 갯수를 구할 때, ball의 갯수에서 strike의 갯수를 빼주는 것이 중요하다 

그 이유는, 예를들어 정답이 123 일 때,  132는 1 스트라이크 3볼인가? 아니면 1스트라이크 2볼인가? 물론 후자이다! 그렇기 때문에 빼주는 것이다!

Pain Point

이 문제는 프로그래머스에서 완전탐색이라는 카테고리에 포함되었기 때문에 쉽게 풀 수 있었다. 하지만, 완전탐색에 있지 않았다면, 무슨 특별한 풀이법이 있지

않을까 생각하면서 많은 시간을 허비했을 것이다. 왠지... 완전탐색은 효율적이지 못한 풀이라고 생각하는 고정관념이 있기 떄문이다.

하지만 이와 같이 경우의 수가 적다면, 완전탐색이 좀 더 직관이지 않을까?

그리고 이 문제를 풀면서.. 뭔가 옛날 생각이 났다. 예전에 학원에 등록하기 전에 간단하게 숫자 야구를 구현한적 있다. 그때 볼의 갯수를 위에 알고리즘처럼 

구현을 했던 기억이 있다. 그리고 그 부분을 피드백을 받아 수정한적이 있었다. 왜냐면, ball이 strike에 의존적이기 때문이었다.