[프로그래머스] 비밀 코드 해독 (C++)

링크: https://school.programmers.co.kr/learn/courses/30/lessons/388352

프로그래머스

풀이

조합을 사용하여 가능한 모든 비밀번호의 경우의 수를 구하고, 조건을 만족하는지 확인하면 되는 간단한 문제이다.

 

조합

void backtracking(int n, vector<int> vec, vector<vector<int>> q, vector<int> ans){
    if (vec.size() == 5){
        if (canPassword(n, vec, q, ans)){
            answer++;
        }
        return;
    }
    
    int i = 1;
    if (vec.size()){
        i = vec.back()+1;
    }
    for (i; i <= n; i++){
        if (!selected[i]){
            selected[i] = true;
            vec.push_back(i);
            backtracking(n, vec, q, ans);
            vec.pop_back();
            selected[i] = false;
        }
    }
}

조합은 백트래킹을 사용하여 구현 가능하다.

비밀번호의 길이는 5로 고정되어있으므로 길이가 5일 때 종료 조건을 설정해주었고

(1, 2, 3, 4, 5)와 (1, 3, 4, 5, 2)와 같이 같은 숫자들로 이루어진 경우가 생기지 않도록 설정해주었다.

 

비밀번호 조건 확인

bool canPassword(int n, vector<int> password, vector<vector<int>> q, vector<int> ans){
    for (int i = 0; i < q.size(); i++){
        int targetCounts = 0;
        for (int j = 0; j < 5; j++){
            int target = q[i][j];
            for (int k = 0; k < 5; k++){
                if (target == password[k]){
                    targetCounts++;
                    break;
                }
            }
        }
        if (targetCounts != ans[i]){
            return false;
        }
    }
    return true;
}

간단하게 3중 for문을 사용하여 모든 조건을 만족하는 경우에만 true를 리턴하도록 설정해주었다.

 

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int answer = 0;
bool selected[31];

bool canPassword(int n, vector<int> password, vector<vector<int>> q, vector<int> ans){
    for (int i = 0; i < q.size(); i++){
        int targetCounts = 0;
        for (int j = 0; j < 5; j++){
            int target = q[i][j];
            for (int k = 0; k < 5; k++){
                if (target == password[k]){
                    targetCounts++;
                    break;
                }
            }
        }
        if (targetCounts != ans[i]){
            return false;
        }
    }
    return true;
}

void backtracking(int n, vector<int> vec, vector<vector<int>> q, vector<int> ans){
    if (vec.size() == 5){
        if (canPassword(n, vec, q, ans)){
            answer++;
        }
        return;
    }
    
    int i = 1;
    if (vec.size()){
        i = vec.back()+1;
    }
    for (i; i <= n; i++){
        if (!selected[i]){
            selected[i] = true;
            vec.push_back(i);
            backtracking(n, vec, q, ans);
            vec.pop_back();
            selected[i] = false;
        }
    }
}

int solution(int n, vector<vector<int>> q, vector<int> ans) {
    backtracking(n, {}, q, ans);    
    
    return answer;
}