프로그래머스 문제 풀이 숫자 야구

문제 URL 숫자 야구

Contents

1. 문제 지문 파악하기
2. 구르미의 알고리즘 풀이

문제 지문 파악하기

이번에도 문제의 입력을 통해서, 문제를 파악해보도록 하겠습니다. 다음은, 첫 번째 입력입니다.

 

입력:
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가지입니다.

 

1. 123 ~ 987까지 각 자릿수가 겹치지 않은 숫자들을 어떻게 만들 것인가?
2. 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가지를 생각해볼 수 있습니다.

 

1. DFS 알고리즘을 이용하여, 3자리 숫자를 만드는 방법
2. 재귀 알고리즘을 이용하여 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의 값을 읽어 필요한 후보군을 추출하면 됩니다.

구르미의 알고리즘 풀이

"문제 지문 파악하기"를 토대로 세운 알고리즘을 순서대로 나열하면 다음과 같습니다.

 

1. 야구 게임에 필요한 모든 숫자들을 저장하는 candidates를 만들어줍니다.
2. baseball을 순회합니다.
   1. baseball = (request, strikes, balls)
   2. candidates에서 request에 대해서, 같은 점수를 지닌 cadidate를 추출합니다.
3. 이렇게 추출된 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 알고리즘 이용하는 것 대비, 코드 량이 반 이상 줄어드는 것을 볼 수 있습니다. 파이썬.. 짜릿해..