[프로그래머스 / C++] 숫자 야구 풀이

문제

 

<문제 설명>

 

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

 

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

 

 

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

 

예를 들어, 아래의 경우가 있으면

 

• A : 123 B : 1스트라이크 1볼.
• A : 356 B : 1스트라이크 0볼.
• A : 327 B : 2스트라이크 0볼.
• A : 489 B : 0스트라이크 1볼.

 

이때 가능한 답은 324와 328 두 가지입니다.

 

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

 

 

<제한사항>

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

 

https://programmers.co.kr/learn/courses/30/lessons/42841

코딩테스트 연습 - 숫자 야구

 

 

 

문제 풀이

 

완전 탐색 문제인 만큼 모든 정답의 경우의 수를 고려해 문제를 풀었습니다. 

 

1. 숫자 야구의 정답이 될 수 있는 수를 모두 생성해 candidate 벡터에 저장한다.

2. candidate의 원소 중 주어진 입력에 부합하지 않는 것을 삭제한다. 

 

 

1. 숫자 야구의 정답이 될 수 있는 수를 모두 생성해 candidate 벡터에 저장한다.

1~9까지의 수 중 중복 없이 세 가지 숫자를 골라 정답을 만들기 때문에 정답은 123 이상 987 이하의 수입니다. 가능한 모든 답을 만들 때, 0이 들어가거나 같은 숫자가 2번 이상 들어가는 경우는 제외했습니다. 

 

 

2. candidate의 원소 중 주어진 입력에 부합하지 않는 것을 삭제한다. 

임의의 수 n이 질문에 부합하는 정답 후보인지 판별하는 함수 isCandidate를 정의했습니다. 볼과 스트라이크의 개수를 세서 입력값과 같다면 true, 다르면 false를 반환합니다. 

 

 

코드 48~51라인에서 candidate 원소를 삭제하지 않을 경우에만 j++을 해준 것은 erase 함수를 사용하면 삭제된 데이터 다음 데이터가 자동으로 한 칸씩 앞으로 당겨지기 때문입니다. 

참고: https://backhugger.tistory.com/45

[C++] 벡터에서 std::erase로 요소 삭제시 주의사항

 

 

 

 

소스코드

 

// 숫자 야구
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// n이 질문에 맞는 후보자인지 판별하는 함수
bool isCandidate(string n, vector<int> question) {
    int strike = 0, ball = 0;
    string q_num = to_string(question[0]); // 질문한 세 자리의 수
 
    for (int i = 0; i < 3; i++) {
        // 볼
        if (q_num[i] == n[0] || q_num[i] == n[1] || q_num[i] == n[2])
            ball++;
        // 스트라이크
        if (q_num[i] == n[i]) {
            strike++;
            ball--; // 스트라이크일 경우 볼이 아니므로 1을 빼준다.
        }
    }
 
    // 질문의 스트라이크, 볼의 수와 일치하는지 반환
    return (strike == question[1] && ball == question[2]);
}
 
int solution(vector<vector<int>> baseball) {
    vector<string> candidate;  // 답이 될 수 있는 수를 저장하는 벡터
    
 
    // 숫자 야구의 가능한 모든 답 만들기
    for (int i = 123; i <= 987; i++) {
        string s = to_string(i);
        // 0이 들어가는 경우 제외
        if (s[0] == '0' || s[1] == '0' || s[2] == '0')
            continue;
        // 같은 숫자가 있는 경우 제외
        if (s[0] == s[1] || s[0] == s[2] || s[1] == s[2])
            continue;
 
        candidate.push_back(s);
    }
 
    for (int i = 0; i < baseball.size(); i++) {
        for (int j = 0; j < candidate.size();) {
            // 질문에 부합하지 않는 정답 후보를 제거한다
            if (!isCandidate(candidate[j], baseball[i]))
                candidate.erase(candidate.begin() + j);
            else
                j++;
        }
    }
 
    
    // 정답 후보의 개수 반환
    return candidate.size();
}

테스트 결과

 

 

 

 

 

 

 

공부한 것을 정리한 내용입니다. 수정할 부분이 있다면 알려주시면 감사하겠습니다 :)