프로그래머스 문제 풀이 숫자 야구
문제 URL 숫자 야구
Contents
- 문제 지문 파악하기
- 구르미의 알고리즘 풀이
문제 지문 파악하기
이번에도 문제의 입력을 통해서, 문제를 파악해보도록 하겠습니다. 다음은, 첫 번째 입력입니다.
입력:
baseball = [ [123, 1, 1], [356, 1, 0], [327, 2, 0], [489, 0, 1] ]
여기서, 정답이 될 수 있는 경우의 수를 구합니다. 어떻게 구할 수 있을까요? 실제로 알아보기 위해서는 야구 게임을 해보는 수밖에 없습니다. 먼저, 야구게임에서 만들 수 있는 수들은 123 ~ 987까지 각 자릿수가 겹치치 않는 수들입니다.
candidate = [123, 124, 125, ... , 987] //각 자릿수는 겹치지 않습니다.
이제 1Round를 시작해보죠.
request = 123
strikes = 1
balls = 1
123을 부를 때, 1strike 1ball입니다. 이 경우, 1자릿수는 자리와 숫자가 일치, 1자릿수는 자리는 다르지만, 숫자가 일치하는 경우입니다. 이 때 후보군은 다음과 같이 줄일 수 있습니다.
candidates = ['134', '135', '136', '137', '138', '139', '142', '152', '162', '172', '182', '192', '243', '253', '263', '273', '283', '293', '324', '325', '326', '327', '328', '329', '413', '421', '513', '521', '613', '621', '713', '721', '813', '821', '913', '921']
이제 2Round입니다.
request = 356
strikes = 1
balls = 0
1Round를 통해 줄어든 후보군 candidates에서, 356에 대해서 1strike 결과를 지닌 것들만 다시 추출합니다.
candidates = ['152', '324', '327', '328', '329']
이렇게 계속 Round를 반복하면 됩니다. 다음은 각 Round에 따라 줄여진 candidates를 나타냅니다.
3Round
request = 327
strikes = 2
balls = 0
candidates = ['324', '328', '329']
4Round
request = 489
strikes = 0
balls = 1
candidates = ['324', '328']
이렇게 반복해서 얻어진 candidates의 길이를 반환하면 됩니다. 즉 답은 2입니다. 여기서 중요한 것은 다음 2가지입니다.
- 123 ~ 987까지 각 자릿수가 겹치지 않은 숫자들을 어떻게 만들 것인가?
- request, candidate를 비교해서 스트라이크 개수와, 볼 개수를 어떻게 구할 것인가?
먼저 쉬운 스트라이크 개수, 볼 개수를 구해봅시다. 입력이 request, candidate일 때, 이들은 모두 3자릿수 문자열입니다. 스트라이크는 자리와, 해당 숫자가 일치해야 합니다.
즉, 자릿수 i에 대해서 다음 수식이 성립되면, 스트라이크로 판단할 수 있습니다.
request[i] == candidate[i]
볼은 해당 숫자는 존재하지만, 자릿수는 일치하지 않을 때 볼입니다. 그렇다면, 자릿수 i에 대해서 다음 수식이 성립됩니다.
request[i] != candidate[i] && request[i] in candidate
따라서 다음 함수로, request, candidate에 대한 점수를 두할 수 있습니다.
def get_score(request, number):
strikes, balls = (0, 0)
for i in range(3):
if request[i] == number[i]:
strikes += 1
elif request[i] in number:
balls += 1
return (strikes, balls)
이번에는 각 자릿수의 숫자들이 모두 다른 숫자들을 만들어내는 방법입니다. 크게 3가지를 생각해볼 수 있습니다.
- DFS 알고리즘을 이용하여, 3자리 숫자를 만드는 방법
- 재귀 알고리즘을 이용하여 3자리 숫자를 만드는 방법
- 3중 For문을 통해서, 3자리 숫자를 만드는 방법
일단 3번은 쉽습니다. 파이썬의 경우, 다음처럼 만들 수 있지요.
numbers = [ str(x) for x in range(1, 10) ] candidates = [ numbers[x] + numbers[y] + numbers[z] for x in range(9) for y in range(9) for z in range(9) if x != y and y != z and z != x ]
numbers = [ str(x) for x in range(1, 10) ]
candidates = [
numbers[x] + numbers[y] + numbers[z]
for x in range(9)
for y in range(9)
for z in range(9)
if x != y and y != z and z != x
]이렇게 만들면, 쉽습니다. 그러나 저는 굳이 이번엔 DFS 알고리즘을 통해서, 만들어보겠습니다. 먼저 다음이 전역적으로 필요합니다.
numbers = [ str(x) for x in range(1, 10) ] graph = [ [ 1 if x != y else 0 for x in range(9) ] for y in range(9) ]
numbers = [ str(x) for x in range(1, 10) ]
graph = [ [ 1 if x != y else 0 for x in range(9) ] for y in range(9) ]
numbers는 우리가 참조할 "1" ~ "9"까지의 문자열들입니다.
모든 숫자들은 자신을 제외한 나머지 정점을 이동할 수 있습니다. 즉, 정점 "1"에서 다른 정점으로 이동할 수 있는 곳은 "2" ~ "9"까지입니다. 이것을 표현한 것이 graph입니다.
다음은 DFS 알고리즘입니다. DFS를 깊이 설명하지는 않겠습니다. 다음 코드를 찬찬히 살펴보신 후, 어떻게 동작할지 한 번 손으로 그려보시면, 제가 무엇을 말하는지 아실 수 있을 겁니다.
def dfs(results, is_visit, here, string):
if is_visit[here]:
return
is_visit[here] = True
string += numbers[here]
if (len(string) == 3):
results.append(string)
return
for there in range(9):
if is_visit[there] == False and graph[here][there] == 1:
dfs(results, is_visit, there, string)
is_visit[there] = False
여기서 중요한 것은 문자열의 길이가 3일 경우, results 넣어주어야 합니다. 즉, 탈출 조건이 방문한 지점을 재방문할 경우 외에 한 가지 더 있는 것이죠.
또한 DFS 탐색이 끝나면, is_visit[there]을 False 시키는 구문입니다. 파이썬의 경우, 모든 것이 참조로 돌아가기 떄문에, 이러한 구문이 필요합니다.
이 dfs를 토대로 candidates를 만들어주면 됩니다.
def solution(baseball): candidates = [] for i in range(9): is_visit = [ False ] * 9 dfs(candidates, is_visit, i, "") # baseball 토대로 candidates 추출
def solution(baseball):
candidates = []
for i in range(9):
is_visit = [ False ] * 9
dfs(candidates, is_visit, i, "") # baseball 토대로 candidates 추출
시작점은 1~9가 될 수 있으므로 이렇게 DFS를 9번 돌려주어야 한다는 것이 중요합니다. 이후 부터는, 이렇게 만들어진 모든 경우의 수 candidates에 대해서 baseball의 값을 읽어 필요한 후보군을 추출하면 됩니다.
구르미의 알고리즘 풀이
"문제 지문 파악하기"를 토대로 세운 알고리즘을 순서대로 나열하면 다음과 같습니다.
- 야구 게임에 필요한 모든 숫자들을 저장하는 candidates를 만들어줍니다.
- baseball을 순회합니다.
- baseball = (request, strikes, balls)
- candidates에서 request에 대해서, 같은 점수를 지닌 cadidate를 추출합니다.
- 이렇게 추출된 candidates의 길이를 반환합니다.
다음을 코드로 나타내면 다음과 같습니다. 먼저 PYTHON 코드입니다.
PYTHON 코드
# "1" ~ "9" 문자열을 저장하는 리스트
numbers = [ str(x) for x in range(1, 10) ]
# "1" ~ "9"의 관계를 표현하는 그래프
graph = [ [ 1 if x != y else 0 for x in range(9) ] for y in range(9) ]
def dfs(candidates, is_visit, here, string):
"""DFS 알고리즘을 통해 모든 경우의 수를 만들어줍니다."""
if is_visit[here]:
return
is_visit[here] = True
string += numbers[here]
if (len(string) == 3):
candidates.append(string)
return
for there in range(9):
if is_visit[there] == False and graph[here][there] == 1:
dfs(candidates, is_visit, there, string)
is_visit[there] = False
def get_score(request, number):
"""request, number를 비교하여, 점수(스트라이크 개수, 볼 개수)를 얻습니다."""
strikes, balls = (0, 0)
for i in range(3):
if request[i] == number[i]:
strikes += 1
elif request[i] in number:
balls += 1
return (strikes, balls)
def solution(baseball):
# 1. 야구 게임에서 생성될 수 있는 모든 경우의 수를 만들어줍니다.
candidates = []
for i in range(9):
is_visit = [ False ] * 9
dfs(candidates, is_visit, i, "")
# 2. baseball을 순회합니다.
# 2-1. baseball = (request, strikes, balls)
# 2-2. candidates에서 request에 대해서, 같은 점수를 지닌 cadidate를 추출합니다.
for (request, strikes, balls) in baseball:
candidates = [ number for number in candidates if get_score(str(request), number) == (strikes, balls) ]
# 3. 이렇게 얻은 후보군 candidates의 길이를 반환합니다.
answer = len(candidates)
return answer
다음은 CPP 코드입니다. 알고리즘은 동일합니다.
CPP 코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int CANDIDATE_LENGTH = 3;
const int N = 9;
const vector<string> numbers = {"1", "2", "3", "4", "5", "6", "7", "8", "9"};
const vector< vector<int>> graph = {
{ 0, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 0, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 0 }
};
void dfs(vector<string> & results, vector<bool> & is_visit, int here, string str) {
if (is_visit[here]) {
return;
}
is_visit[here] = true;
str += numbers[here];
if (str.size() == CANDIDATE_LENGTH) {
results.push_back(str);
return;
}
for (int there=0; there<N; there++) {
if (!is_visit[there] && graph[here][there]) {
dfs(results, is_visit, there, str);
is_visit[there] = false;
}
}
}
pair<int, int> get_score(string request, string candidate) {
int strikes = 0, balls = 0;
for (int i=0; i<CANDIDATE_LENGTH; i++) {
if (request[i] == candidate[i]) {
strikes += 1;
} else if (find(candidate.begin(), candidate.end(), request[i]) != candidate.end()) {
balls += 1;
}
}
return make_pair(strikes, balls);
}
int solution(vector<vector<int>> baseball) {
vector<string> candidates;
for (int i=0; i<N; i++) {
vector<bool> is_visit(N);
dfs(candidates, is_visit, i, "");
}
for (const auto game : baseball) {
vector<string> tmp;
for (const auto & candidate : candidates) {
auto score = get_score(to_string(game[0]), candidate);
if (score.first == game[1] && score.second == game[2]) {
tmp.push_back(candidate);
}
}
candidates = tmp;
}
int answer = candidates.size();
return answer;
}
파이썬의 경우, dfs 알고리즘 필요 없이, itertools.permutations 함수로 훨씬 간단하게, 1~9까지 3개를 골라오는 모든 경우의 수를 만들수 있습니다. 따라서, 코드량을 상당히, 줄일 수 있습니다. 코드는 다음과 같습니다.
PYTHON 코드
def get_score(request, number):
# 이전과 동일
pass
def solution(baseball):
from itertools import permutations
numbers = [ str(x) for x in range(1, 10) ]
candidates = [ ''.join(result_set) for result_set in permutations(numbers, 3) ]
for (request, strikes, balls) in baseball:
candidates = [ number for number in candidates if get_score(str(request), number) == (strikes, balls) ]
answer = len(candidates)
return answer
DFS 알고리즘 이용하는 것 대비, 코드 량이 반 이상 줄어드는 것을 볼 수 있습니다. 파이썬.. 짜릿해..