진행한 코딩 테스트 문제를 기록하기 위한 글 입니다.
해당 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/451808
문제 설명
1~9까지 숫자 중복 없는 숫자 야구를 진행한다.
질문 기회 n번이 주어지고, 질문을 할 때 마다 실제 정답에 맞춰서 "xS yB" 형태로 단서를 획득하는데, 이러한 단서들을 통해 실제 정답을 n번 내에 맞추는 문제이다.
가장 먼저, 내가 직접 숫자 야구를 플레이 해본다고 생각하고 몇가지 조건들을 생각해보았다.
- 제외되는 숫자 찾기
- 예를 들어서 9라는 숫자가 확실하게 제외된다면 추후 9를 신경쓰지 않아도 된다.
- 정답에 맞는 숫자 모두 찾기
- S가 아니더라도 4B를 도출할 수 있다면 숫자 재배치는 기존 목록을 보고 간단하게 처리할 수 있다.
- 그렇게 B들을 찾으면 S가 될 때 까지 숫자 재배치하기
내가 숫자 야구를 플레이하는걸 생각해보면 대략적으로 위와 같은 순서대로 풀이를 진행할거라는 생각이 들어 일단은 n의 조건은 신경쓰지 않고 생각의 흐름에 맞춰 로직을 먼저 작성하려 했다.
일단 확실하게 0S 0B라는 결과가 만약에라도 나오게되면 그 숫자들은 전부 배제할 수 있게되고, 반대로 4S가 나오면 정답이기에 그 숫자를 반환할 수 있다.
하지만 대부분의 질문은 0 혹은 4 대신 1,2,3의 결과를 반환하기 때문에 이 정보들을 어떻게 처리할지 고민해봤다.
내가 플레이 한다고 했을 때, 스트라이크와 볼을 합한 카운트가 1개밖에 없다면, 다음엔 방금 물어보지 않은 숫자들로만 물어볼거같고, 카운트 2개면 기존 숫자에서 2개 그리고 새 숫자에서 2개를 물어볼거 같고, 카운트가 3개라면 기존 숫자 3개 새 숫자에서 1개를 물어볼 것 같았다.
카운트 1개 기준, 전부 새로운 숫자를 물어보기 위해 방금 질문의 숫자를 가져와서 Linq를 사용하며 제외할 숫자를 제외하고, 새 질문용 숫자 조합을 만드는 부분까진 별 문제가 없었지만, 기존 숫자와 새 숫자를 같이 물어보는 과정을 어떻게 처리해야할지 감을 잡지 못하였다.
남겨야 하는 기존 숫자는 아무리 봐도 기존 리스트를 보고 판단해야 할거같은데, 단순하게 머릿속으로 생각하기엔 무리가 있어서 이 시점에서 실제로 숫자야구를 플레이 해보기로 했다.
AI를 이용해서 1~9, 숫자 중복 없이 랜덤한 숫자를 정답으로 정해두고 질문에 맞춰 스트라이크와 볼 카운트를 알려달라고하며 플레이를 진행했다.
여러번의 플레이를 진행하면서, 숫자 야구 플레이를 규칙화 하기 위한 많은 시도들 끝에 몇가지 규칙의 디테일을 잡을 수 있었다.
-
1234, 5678 두 질문을 첫번째와 두번째 질문으로 고정한다.
- 이 과정을 통해서 9가 사용되는지, 아닌지까지 확정할 수 있기 때문에 모든 숫자에 대한 기본적인 정보를 파악할 수 있다.
-
세번째 질문부터는 기존 정보를 토대로 질문할 숫자를 물어봐야 하는데, 가능한 한 정답 후보를 물어본다.
- 즉, 1234에서 2B, 5678에서 1S가 나왔다면 1259 같은 방식으로 모든 숫자가 정답이 될 수 있는 가능성으로 조합해서 물어본다.
-
이때, 1234에서의 두 숫자는 12, 13, 14, 24 등 여러 조합이 가능한데, 여러 고민 끝에 숫자별로 우선순위를 부여해서 가장 적게 물어본 숫자들 조합으로 물어보기로 한다.
-
우선순위는 처음에는 전부 동일하며, 질문을 진행할 수록 질문한 숫자의 우선순위가 점점 줄어들게 된다.
-
위 모든 조건들을 고려해서, 새 질문을 하기 위한 숫자 후보를 만들고 나서, 기존 질문 리스트와 비교해서 현재 질문이 가능성이 있는 질문인지 확인한 이후 최종적으로 실제 질문에 적용한다.
오랜 시간이 걸려 위 규칙들을 발견, 확정하고 이를 로직에 적용해서 문제를 풀어보았다.
구현 코드
using System;
using System.Collections.Generic;
public class Solution
{
//시도해본 리스트, 모든 후보 리스트, 우선순위용 배열
List<(int number, string result)> tryList;
List<int> numberList = new List<int>();
int[] useCount;
public int solution(int n, Func<int, string> submit)
{
//시도 결과를 기록해둘 리스트
tryList = new List<(int number, string result)>();
//숫자 사용 횟수 (우선순위 판정용)
useCount = new int[10];
int tryNum = 0000;
//1234 ~ 9876의 모든 숫자 후보 생성
for (int num = 1234; num <= 9876; num++)
{
int a = num / 1000;
int b = num / 100 % 10;
int c = num / 10 % 10;
int d = num % 10;
//0이 있으면 패스
if (a == 0 || b == 0 || c == 0 || d == 0)
continue;
//중복된 숫자가 있으면 패스
if (a == b || a == c || a == d ||
b == c || b == d ||
c == d)
continue;
//문제 없으면 후보로 추가
numberList.Add(num);
}
//실제 시도 진행(다음 파트에서 설명)
for (int i = 1; i <= n; i++)
...
return tryNum;
}
}한번에 전체 코드를 설명하기엔 코드가 길어서 분리해서 설명하려 한다.
일단 첫번째로는 숫자 야구를 위한 기본 준비 단계로, 각종 리스트나 변수를 선언해둔다.
그 다음으로 1234~9876에서 0이 없고 중복이 없는 모든 경우의 수를 numberList에 저장해둔다.
이렇게 만든 리스트는 다음에 어떤 숫자를 질문할 수 있는지 확인할 때 사용하게 된다.
매번 새 숫자를 전부 가져와서 각종 조건들을 전부 만족하는지 확인하고 가장 우선순위가 높은 숫자를 도출해내고 하는것을 최대한 줄이기 위해, 미리 전체 후보를 만들어두고 결과에 따라 정답이 될 수 없는 후보숫자들은 전부 리스트에서 제외하는 방식으로 코드가 돌아간다.
예를 들어서 1234에서 0S 0B가 확인되면, 1/2/3/4 네 숫자는 정답 후보일 수 없기 때문에, 전체 후보 리스트에서 해당 숫자들이 포함된 숫자 조합들은 전부 삭제처리가 진행되고, 다음 질문 또한 이 리스트에서 골라가기 때문에 다음에 질문할 숫자를 관리하기 편하다.
//시도할 숫자를 가져와서 질문을 진행하는 핵심 로직
for (int i = 1; i <= n; i++)
{
//시도할 숫자 조합 가져오기
tryNum = GetNewTryNum(tryList);
//사용 횟수 증가(우선 순위 처리용)
AddUseCount(tryNum);
//트라이 진행
string result = submit(tryNum);
//트라이 내역 기록
tryList.Add((tryNum, result));
//만약 4S면 그대로 정답 반환
int strike = result[0] - '0';
if (strike == 4) return tryNum;
//후보 제거
for (int j = numberList.Count - 1; j >= 0; j--)
{
//시도해봐야 하는 리스트를 뒤에서부터 돌면서 문제있는지 확인
if (!NumberCheck(numberList[j]))
{
//문제있다면 후보 제거
numberList.RemoveAt(j);
}
}
//후보가 하나 남으면 정답이란 의미
if (numberList.Count == 1)
{
return numberList[0];
}
}메인 로직의 흐름은 가장 먼저 시도할 숫자를 가져오고, 해당 숫자들의 사용 횟수를 증가시켜준다.
이후 해당 숫자가 정답이 맞는지 질문(submit)하고, 질문한 숫자와 그 결과를 기록해둔다.
결과가 4S라면 현 숫자가 정답이라는 의미가 되기에 바로 숫자를 반환해주고, 그렇지 않다면 다음 질문을 위한 후보 제거 단계로 넘어간다.
후보 제거 단계는 인덱스가 꼬이지 않도록 리스트를 뒤에서부터 돌며 체크를 진행하고, 문제가 있는 후보면 제거하는 방식으로 관리되며, 이러한 과정들을 지나 만약 후보가 단 하나만 남게되면 해당 숫자가 정답이기 때문에 그 하나 남은 숫자를 정답 숫자로 반환해준다.
전체적인 흐름은 이정도 설명만으로 끝이기 때문에 각 주요 메소드들을 확인해봐야 한다.
//시도할 숫자 조합 가져오기
private int GetNewTryNum(List<(int number, string result)> tryList)
{
//첫 트라이는 1234, 두번째는 5678 고정
if (tryList.Count == 0)
{
numberList.Remove(1234);
return 1234;
}
else if (tryList.Count == 1)
{
numberList.Remove(5678);
return 5678;
}
//우선순위에 맞는 다음 숫자 가져오기
int bestNum = numberList[0];
int bestPriority = GetPriority(bestNum);
foreach (int number in numberList)
{
int priority = GetPriority(number);
//사용 횟수 총합이 더 낮으면 변경
if (priority < bestPriority)
{
bestPriority = priority;
bestNum = number;
}
}
return bestNum;
}이번 질문에 사용될 숫자 조합을 반환해주는 메소드로, 첫 질문은 1234, 두번째 질문은 5678로 고정된다.
세번째 질문부터는 리스트를 돌면서 가장 우선순위가 높은 조합을 하나 가져와서 반환해주도록 되어있다.
//우선순위 계산
private int GetPriority(int number)
{
int a = number / 1000;
int b = number / 100 % 10;
int c = number / 10 % 10;
int d = number % 10;
return useCount[a] + useCount[b] + useCount[c] + useCount[d];
}우선순위 체크는 간단한데, 이번에 확인할 숫자를 1000, 100, 10, 1의 자리로 각각 분해해서 현재까지 사용된 카운트를 전부 더해서 우선순위를 구한다.
즉 숫자별 우선순위의 총합을 현재 숫자 조합의 우선순위 정도로 보고, 이 총합이 가장 낮은 숫자 조합이 이번 질문 대상 숫자가 된다.
이렇게 현재 리스트에 남은 모든 숫자 조합의 우선순위를 비교해서 가장 우선순위가 낮은 숫자를 하나 반환해주면, 이 숫자는 사용 횟수 증가 이후 실제 submit을 진행한다.
사용횟수 증가도 우선순위처럼 각 자릿수를 분해해서 +1을 진행해주는 간단한 형태로 되어있기 때문에 사용횟수 증가 코드는 스킵한다.
submit 이후의 과정을 다시 설명하자면, submit 결과 기록, 4S인 경우 정답 반환, 그리고 후보 제거 및 후보 카운트 확인 단계로 넘어간다.
//후보 제거
for (int j = numberList.Count - 1; j >= 0; j--)
{
//시도해봐야 하는 리스트를 뒤에서부터 돌면서 문제있는지 확인
if (!NumberCheck(numberList[j]))
{
//문제있다면 후보 제거
numberList.RemoveAt(j);
}
}
//후보가 하나 남으면 정답이란 의미
if (numberList.Count == 1)
{
return numberList[0];
}코드를 다시 보면 뒤에서부터 NumberCheck 메소드를 통해 문제 여부를 판단하고 제거하도록 되어있기 때문에 NumberCheck 메소드를 확인해야한다.
//숫자 조합을 하나 가져와서 문제 없는지 확인
private bool NumberCheck(int number)
{
//확인하려는 숫자
int[] checkNums =
{
number / 1000,
number / 100 % 10,
number / 10 % 10,
number % 10
};
//시도했던 결과 정보 리스트
foreach (var tried in tryList)
{
int strike = 0;
int ball = 0;
//기존에 확인했던 숫자
int[] tryNums =
{
tried.number / 1000,
tried.number / 100 % 10,
tried.number / 10 % 10,
tried.number % 10
};
for (int i = 0; i < 4; i++)
{
//같은 자리에 같은 숫자가 존재하면 스트라이크 추가
if (checkNums[i] == tryNums[i])
{
strike++;
continue;
}
for (int j = 0; j < 4; j++)
{
//검증해야하는 숫자 목록에 현재 확인중인 기존 숫자가 존재하면 볼 추가
if (tryNums[i] == checkNums[j])
{
ball++;
break;
}
}
}
//기존 리스트의 결과 가져오기
int targetStrike = tried.result[0] - '0';
int targetBall = tried.result[3] - '0';
//기존 리스트와 스트라이크, 볼이 하나라도 다르면 실패
if (strike != targetStrike || ball != targetBall)
return false;
}
//문제 없으면 성공
return true;
}이 메소드는 현재 확인하려는 숫자를 1000, 100, 10, 1의 자리로 각각 분해하고, 지금까지 시도했던 결과 정보 리스트를 돌면서 리스트의 숫자도 각각 분해하면서 진행된다.
추가적인 for문을 통해 같은 i 인덱스로 두 숫자 조합을 그대로 확인하면 같은 자릿수를 확인할 수 있는데, 만약 이 두 숫자의 같은 자릿수의 숫자가 같으면 서로 스트라이크가 되기에 스트라이크를 추가해준다.
추가적인 for문을 통해 j 인덱스로 확인하려는 숫자를 전부 돌아주면 다른 자릿수에 있는 같은 숫자를 확인할 수 있는데, 이를 통해서 볼 카운트도 추가해준다.
이 다음은 기존 결과 리스트의 스트라이크와 볼 카운트를 가져와서 온전하게 동일한지 확인하고, 이를 모든 결과 리스트를 돌면서 확인한 후에도 문제가 없으면 결론적으로 true를 반환하게 된다.
중간에 문제가 하나라도 있으면 false가 반환되는데, ! NumberCheck(numberList[j]) 형태로 검사중이기에 false 반환 시 해당하는 숫자가 제거된다.
그럼 여기서, 정답 숫자도 모르는데 왜 기존 질문 목록과 비교할 수 있는지에 대한 의문이 생길 수 있다.
만약 1234가 1S 1B라고 가정하면 정답은 모르겠지만, 최소한 그 정답은 1234를 질문했을 때 정확하게 1S 1B가 나온다는 것을 의미한다.
이를 이용해서 후보 하나를 가져와서 그 후보가 진짜 정답이라고 가정해보는 방식을 이용한다.
예를 들어서 4258이라는 숫자를 가져와서 이를 정답이라고 가정해보고 여기에 1234를 비교해보면, 1S 1B가 나온다.
이렇게 실제 기록과 이번 숫자 조합과의 계산 결과가 동일하다면 정답일 가능성이 0은 아니라는 것을 의미한다.
중요한건 정확하게 1S 1B가 나와야 하는 것으로, 1S 0B 혹은 1S 2B와 같이 카운트가 더 적거나 반대로 많은 경우엔 정답 후보와 다르다는 의미가 되어 전부 실패처리가 된다.
질문 리스트가 쌓이다보면 조건이 계속해서 늘어나고, 이는 곧 만족해야 하는 조건이 계속해서 늘어난다는 의미이기 때문에, 정답 후보가 계속해서 줄어들게 된다.
핵심적인 한줄로 요약하면, "이번 후보를 정답이라고 가정하고 과거의 질문을 다시 적용해보았을 때 결과가 그대로 나오는가?" 라는 것이 핵심이다.
이 코드를 제출해보면 90점이라는 점수를 확인할 수 있었다.
