문제 설명

숫자 야구 게임이란 2명이 서로가 생각한 숫자를 맞추는 게임 입니다. 게임해보기

각자 서로 다른 1~9까지 3자리 임의의 숫자를 정한 뒤 서로에게 3자리의 숫자를 불러서 결과를 확인합니다. 그리고 그 결과를 토대로 상대가 정한 숫자를 예상한 뒤 맞힙니다.

1. 숫자는 맞지만, 위치가 틀렸을 때는 볼
2. 숫자와 위치가 모두 맞을 때는 스트라이크
3. 숫자와 위치가 모두 틀렸을 때는 아웃

예를 들어 아래의 조건이 있다면.

A : 123
B : 1S, 1B
A : 356
B : 1S, 0B
A : 327
B : 2S, 0B
A : 489
B : 0S, 1B

이 때 가능한 답은 [324, 328] 두 개 입니다.

질문한 세 자리의 수, 스트라이크의 수, 볼의 수를 담은 2차원 배열 baseball 이 매개변수로 주어질 때, 가능한 답의 개수를 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

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

Solution

처음 문제를 보고서 약 2시간 가량 접근법이 떠오르지 않아 한참을 고민하다가 결국 다른 분들의 블로그를 보고 접근법을 참고하여 해결하였다.

완전 탐색 으로 분류된 문제로, 모든 경우의 수에 대하여 적합 여부를 탐색한다. 여기서 어떻게 적합 여부를 판단할 것인가 가 핵심(접근법)이 되겠다. solution 함수의 인자로 넘겨진 baseball의 세자리 수 값들과 비교하여 스트라이크, 볼이 같은 숫자 가 바로 가능한 답이 된다.

언뜻 생각하면 잘 이해가 되지 않을 수 있다.(내가 직관력이 부족하여 언뜻 이해가 되지 않았다.) 우리가 원하는 것은 모든 순열 에서 임의의 수가 적합한지 여부 를 판단하는 것이다. 여기서 적합할 자격 을 갖기 위해서는 주어진 baseball 의 각 세자리 숫자인 target 과 비교를 해야하는데, target 과 비교할 수를 baseNumber 이라 하자.

그리고 최종적으로 이러한 가능한 답이 몇 개 있는지 return하면 된다.

baseNumber가 [정답이 가능한 수] 가 되기 위해서는 target과 비교했을 때 동일한 Strike, Ball이 나와야 한다. Why? baseNumber가 정답이 되기 위해서는 당연히 target이 정답과 비교한 결과와 같아야 할 것이다. 즉, baseNumber를 정답이라고 가정하고 target과 비교했을 때 동일한 결과가 나와야만 후보가 될 수 있다. 바로 이것이 문제 해결을 위한 핵심적인 접근법이다.

단순한 예를 들어보자. baseball : [123, 1, 1] baseNumber : 132

위와 같이 baseNumber을 132 라는 수를 baseball의 123 과 비교했을 때는 1S/2B 라는 결과가 나온다. 그리고 이 결과는 baseball의 1S/1B 와 다르기 때문에 결과적으로 132 숫자를 갖는 baseNumber은 가능한 답이 될 수 없다. 반면 baseNumber의 값이 324 라면 baseball과 비교시 1S/1B 로 같기 때문에 가능한 답이 될 수 있다.

Code

핵심적인 접근법을 살펴봤으니 이제 코드를 살펴보자. 응집력을 높이기 위해서 메서드를 분할하였다.

전체적인 코드의 흐름을 살펴보면

  1. 모든 순열을 baseballBox(Stack) 에 저장한다. (Recursion 이용)

  2. 저장된 baseballBox 의 요소를 하나씩 꺼내어 비교 대상인 baseball 의 각 요소들과 strike, ball을 비교한다. 이 때 baseNumber 가 모든 baseball 의 요소와 비교하여 가능한 후보가 되었을 때에 카운팅을 해준다. 물론 baseball 의 요소와 비교할 때에도 Recursion 을 이용하여 적합성 여부를 판단하였다.

몇줄 평

  • 접근법에 대한 직관이 부족하기 때문에 더 많은 문제를 풀어보고 더 많이 고민을 해봐야 할 필요가 있다.

  • 2시간 이상 고민해도 접근법이 파악되지 않는다면 다른 사람들의 풀이법에서 접근 법 만 참고하고 직접 구현 한 뒤 왜 이러한 접근법이 나왔는지 스스로 고민해야겠다.

  • 알고리즘 문제풀이 에서도 응집력 높은 메서드 로 분할하는 연습을 자주 해야겠다.

  • 왜 직관이 안떠올랐는지 스스로를 자책하고 괴롭게 하는 과정이 힘들지만 하나하나 풀어가는 뿌듯함이 더 크고 문제풀이를 오랫동안 안했다고 하여 아예 놔버리지 않는게 중요 함을 느꼈다.

참고 및 출처

cheolhojung님 블로그