프로그래머스_완전탐색_숫자야구 (JAVA)

문제 설명 숫자 야구 게임이란 2명이 서로가 생각한 숫자를 맞추는 게임입니다. 게임해보기 각자 서로 다른 1~9까지 3자리 임의의 숫자를 정한 뒤 서로에게 3자리의 숫자를 불러서 결과를 확인합니다. 그리고 그 결과를 토대로 상대가 정한 숫자를 예상한 뒤 맞힙니다.     예를 들어, 아래의 경우가 있으면     이때 가능한 답은 324와 328 두 가지입니다. 질문한 세 자리의 수, 스트라이크의 수, 볼의 수를 담은 2차원 배열 baseball이 매개변수로 주어질 때, 가능한 답의 개수를 return 하도록 solution 함수를 작성해주세요.   제한사항 질문의 수는 1 이상 100 이하의 자연수입니다. baseball의 각 행은 [세 자리의 수, 스트라이크의 수, 볼의 수] 를 담고 있습니다.

 

 

이전 문제들과 마찬가지로 순열 알고리즘을 구현할 수 있으면 쉽게 풀 수 있는 문제입니다. 저는 문제를 잘 못 읽어서 엄청 헤맸습니다. 제한사항에는 없지만 저 위에 보면 "각자 서로 다른 1~9까지 3자리 임의의 숫자를 정한 뒤 서로에게 3자리의 숫자를 불러서 결과를 확인합니다." 라는 문구가 있습니다. 중복이 없고 0이 없는 숫자만 대상으로 한다는 점에 주의해야 합니다. 

 

* 전체 코드

package pojoPrj;

import java.util.ArrayList;
import java.util.List;

class Solution {

	private int count;

	public int solution(int[][] baseball) {

		// 문자열 배열로 변경
		String[][] arr = new String[baseball.length][3];
		for (int i = 0; i < baseball.length; i++) {
			for (int j = 0; j < baseball[i].length; j++) {
				arr[i][j] = String.valueOf(baseball[i][j]);
			}
		}

		// 9P3의 원본 리스트
		List<Integer> nums = new ArrayList<>();
		for (int i = 1; i < 10; i++) {
			nums.add(i);
		}

		// 결과 담을 배열
		int[] result = new int[3];

		// 실행
		permutation(arr, nums, result, 0, 9, 3);
		return count;
	}

	/**
	 * 순열 구하기 (1~9, 중복 없음)
	 * 
	 * @param arr    : 원본 문자열
	 * @param nums   : 1~9 리스트
	 * @param result : 결과 담을 배열
	 * @param depth  : r개중 몇 번째를 찾고 있는지 나타냄
	 * @param n      : 전체 갯수 n
	 * @param r      : 뽑을 갯수 r
	 */
	private void permutation(String[][] arr, List<Integer> nums, int[] result, int depth, int n,
			int r) {

		if (depth == r) {

			if (result[0] != 0) {

				boolean isTrue = true;
				for (int i = 0; i < arr.length; i++) {

					int strike = 0;
					int ball = 0;

					// 같은 숫자 없으므로 모두 비교
					for (int j = 0; j < 3; j++) {

						// strike, ball 있으면 break
						for (int w = 0; w < 3; w++) {

							if (arr[i][0].charAt(j) - '0' == result[w]) {

								if (j == w) {
									strike++;
									break;
								} else {
									ball++;
									break;
								}
							}
						}
					}

					// 제공된 배열에서 정보가 하나라도 다르면 false
					if (!(strike == arr[i][1].charAt(0) - '0')
							|| !(ball == arr[i][2].charAt(0) - '0')) {
						isTrue = false;
					}
				}

				// 제공된 배열과 strike, ball 정보가 모두 맞을 경우
				if (isTrue) {
					count++;
				}

			}
			return;
		}

		// 순열 구하기
		for (int i = 0; i < n - depth; i++) {
			result[depth] = nums.remove(i);
			permutation(arr, nums, result, depth + 1, n, r);
			nums.add(i, result[depth]);
		}
	}
}

 

---

 

순열, 조합 알고리즘은 처음에는 어려웠는데 한 번 이해하고 나면 의외로 원리가 간단해서 응용하는데 별 문제가 없습니다. 만약 {1,1,1} 같이 중복이 허용되는 문제라면 순열 알고리즘에서 배열에 넣었다 뺐다 하는 작업을 제외하면 됩니다. 배열에서 빼는 이유는 자기 자신을 두 번 포함하지 않기 위해서입니다.

 

저 같은 경우는 숫자를 모두 String 타입으로 변경해서 charAt() 메소드로 한글자씩 char 타입으로 가져와 비교를 해줬는데, 순열이 int 형이기 때문에 비교를 위해 '0'을 빼줬습니다. char타입은 일반 숫자가 아니라 아스키코드에서 표현하는 문자입니다. 따라서 숫자 1은 아스키코드가 49이기 때문에 int형으로 변환하면 49가 됩니다. 따라서 바로 직전 아스키 코드인 '0'을 빼주면 "49-48 = 1"이 되어 int형과 정상적으로 비교가 가능해집니다. 

 

		char a = '1';
		System.out.println((int) a); // 49

		char b = '1' - '0';
		System.out.println((int) b); // 1

 

 

순열만 구현하면 되는 문제라 여기서 마무리하겠습니다. 알고리즘 설명은 아래 링크를 참조하시면 됩니다.

 

[JAVA/- 알고리즘 및 자료구조] - 부분집합_재귀함수_멱집합 구하기 (JAVA)

[JAVA/- 알고리즘 및 자료구조] - 부분집합_재귀함수_순열 구하기 (JAVA)

[JAVA/- 알고리즘 및 자료구조] - 부분집합_재귀함수_조합 구하기 (JAVA)