서론
프로그래머스에 기존 코딩 테스트 문제와는 다른 유형의 흥미로운 문제가 나왔다고 한다. 어릴 적(?) 숫자 야구를 많이 하곤 했었는데, 이에 관한 문제다. 문제는 아래 링크에서 읽고 오도록 하자. https://school.programmers.co.kr/learn/courses/30/lessons/451808
풀이
이 문제는 특정 기능을 하는 함수를 주고 그 함수의 결과에 따라 숫자를 추론하여 제한된 호출 횟수 이내에 답안을 제출하여 풀어야 한다.
|
보통 테스트 케이스를 잘 안 주는데, 카카오처럼 그룹에 따른 점수와 제한 사항을 줬다. 각 그룹 별 총점과 제한 사항은 좌측 사진과 같다. 한번에 답안으로 가면 무슨 재미가 있겠습니까? 각 그룹의 제한사항이 담고있는 숫자의 의미에 대해 알아가봅시다. |
우선, 문제의 조건은 1000 ≤ 답 ≤ 9999 이면서 1 ~ 9 중 서로 다른 4개의 수로 이루어져야 한다는 겁니다. 가령 1111 은 답이 될 수 없지만 “1S 3B” 나 “0S 0B” 처럼 결과를 받을 수 있음.
그룹 별 풀이
n = 3024
전체 경우의 수를 뜻하는 것 같다. 9가지의 수가 있으니 중복 없이 4자리를 채우려면 9 * 8 * 7 * 6 = 3024의 가짓수가 나온다.
n = 33
1번째 방법은 너무 비효율적이니까 몇 개 숫자에 들어가는 수를 명확하게 찾아봐. 라고 소리치는 듯 하다.
1111, 2222, 3333, …, 9999 까지 하면 4개의 경우에서 “1S 3B”를 얻을 수 있다. 4개의 숫자에 대해 모든 조합을 찾으면 4!이다. 따라서 9 + 4! = 33의 가짓수가 나온다.
n = 14
2번째 방법을 강화한 방법이다. 1111 부터 9999 까지 조사하면서 처음 1S 3B가 나온 순간 그 숫자를 다음에 한칸씩 이동하며 자리를 찾는 것이다. 예를 들어 보자. 답이 9532 이라고 하겠다. 풀이는 답을 모른다는 가정하에 진행한다.
1111 → 0S 0B : 재낀다.
2222 → 1S 3B : 2가 들어가는군!
3233 → 2S 2B 아니면 1S 3B 아니면 4B : 2S 2B라면 2의 위치를 찾은 것. 나머지는 3도 답에 들어간다로 해석.
…(0S 0B 나오는 것들은 생략)
5525 → 2S 2B 아니면 1S 3B 아니면 4B : 2S 2B라면 2의 위치를 찾은 것. 나머지는 5도 답에 들어간다로 해석.
…(0S 0B 나오는 것들은 생략)
9992 → 2S 2B 아니면 1S 3B 아니면 4B : 2S 2B라면 2의 위치를 찾은 것. 나머지는 9도 답에 들어간다로 해석.
이처럼 0S 0B 가 나온다면 처음 1S 3B 나온 수의 위치를 유지하고 0S 0B가 아닌 결과가 나온다면 2를 다음 위치로 이동 시킨다. 이중 2S 2B가 나온 것이 2의 위치이다.
⇒ 총 9번의 실행으로 숫자 1개의 위치를 알게 된다.
이러면 숫자 3개가 남는다 3, 5 ,9
얘네도 마찬가지로 아무 숫자 하나 집어서 반복한다.
3352 → 3532 → 5332 (5의 위치가 보이시죠?)
이러면 3S 1B 나오는게 있을 것이다. 그게 5의 위치다.
⇒ 총 3번의 실행으로 다음 숫자 1개의 위치를 알게 된다.
나머지 3,9 에 대해서도 진행해준다.
3592 → 9532 (3, 9가 보이죠?)
이러면 4S 0B 나오는게 있을 것이다. 그게 답이다.
⇒ 총 2번의 시행으로 다음 숫자 2개의 위치를 알게 된다.
9 + 3 + 2 = 14의 가짓수가 나온다.
n = 6, 9
하.. 이쯤오니 6,9 숫자 자체에 대한 의미를 파악하지 못하겠더군요. 그래서 최악의 상황에서도 컴퓨터가 맞출 수 있는 방법을 생각하는 것으로 바꿨습니다. 결과값이 주는 정보의 가치로 방향을 바꿔봤어요. 즉, 결과로 나오는 0S 0B, 1S 0B, 0S 1B, …, 0S 4B 이 친구들에 대한 가치로 말이죠.
저희가 가진 전체 경우의 수는 3024개 이고 결과가 주는 정보를 통해 필터링하면 각 시행에 대한 최선의 정보만 남는 것이죠. 이걸 다음 시행에 반복 적용하는 거구요.
그럼 증명은 할 수 있니? 라고 스스로에게 되물어 봤어요. 아니요..? 라고 답하더군요 (아마 수학과는 알지 않을까요???)
제 생각은 특정 수에 대한 결과를 얻었을 때 0S 0B, …, 0S 4B 중 필터링이 제일 안되는 결과가 있을 거에요. 그러면 한 번 제출했을 때 필터링 되는 비율을 구할 수 있습니다. 최악의 경우에도 3024개 -> 1개로 만드는 제출 횟수를 알 수 있게 되죠. (문제가 n=6이 마지막 조건이니 아마 평균적으로 5.xx 번이라는 결론이 나올 듯 싶어요)
소스 코드
n = 6, 9 부분에서 내린 결론에 따른 코드에요
import java.util.function.Function;
import java.util.*;
class Solution {
public int solution(int n, Function<Integer, String> submit) {
List<Integer> list = new ArrayList<>();
insertAllCase(list);
while (list.size() != 1) {
int num = list.get(0);
String result = submit.apply(num);
list = filterList(list, num, result.charAt(0) - '0', result.charAt(3) - '0');
}
return list.get(0);
}
// 3024개 전체 경우 생성
private void insertAllCase(List<Integer> list) {
for (int a = 1; a <= 9; a++) {
for (int b = 1; b <= 9; b++) {
if (a == b) continue;
for (int c = 1; c <= 9; c++) {
if (a == c || b == c) continue;
for (int d = 1; d <= 9; d++) {
if (a == d || b == d || c == d) continue;
list.add(1000 * a + 100 * b + 10 * c + d);
}
}
}
}
}
// submit 결과에 따른 list 업데이트
private List<Integer> filterList(List<Integer> list, int num, int strike, int ball) {
List<Integer> newList = new ArrayList<>();
String strNum = Integer.toString(num);
Set<Character> numSt = new HashSet<>();
numSt.add(strNum.charAt(0));
numSt.add(strNum.charAt(1));
numSt.add(strNum.charAt(2));
numSt.add(strNum.charAt(3));
for (int ele : list) {
String strEle = Integer.toString(ele);
int strikeCnt = 0;
int ballCnt = 0;
for (int i = 0; i < 4; i++) {
if (strNum.charAt(i) == strEle.charAt(i)) {
strikeCnt++;
} else if (numSt.contains(strEle.charAt(i))) {
ballCnt++;
}
}
if (strikeCnt == strike && ballCnt == ball) {
newList.add(ele);
}
}
return newList;
}
}
결과
소감
한 문제를 다섯 문제로 쪼개서 풀어보니 출제자가 변별하고자 하는 선(?) 같은 것을 나름대로 느낄 수 있었던 듯 하다.
기존의 코테 유형 말고도 새로운 유형이 나오려는 듯 한데, 유형은 바뀌었지만 사고력을 요한다는 점에서 코딩 테스트의 본질은 바뀌지 않았다.
다만, 회사에 가면 이미 만들어진 모듈들이 있는데 잘 쓸 수 있겠니? 하는 듯 했다.
