lv2) 비밀코드 해독

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

프로그래머스

 

제한 시간 60분, 문제 자체를 이해하는게 40분정도 걸린 것 같다.

조합으로 문제 접근법은 맞았지만, 간간히 실수가 있었다.

1. recursion 매개변수로 val + 1 이 아닌 num +1을 함으로써 제대로 조합 값이 구성되지 않았다.
2. 조합 배열의 사이즈(mask 사이즈)가 무조건 5라고 생각하지 않았다. ans의 사이즈 즉 m을 따라 간 다고 생각했다. 그러나 문제에서 조합 배열 사이즈가 5이며 m(시도횟수)은 10까지 범위가 있는 것을 확인할 수 있다.

문제만 빠르게 이해하면 금방 풀 수 있기에, 위와 같은 실수를 범하지 말자.

#include <string>
#include <vector>
#include<iostream>
using namespace std;
//n 이 30이하기에 재귀 통한 조합 가능
//Permutation 통해 Combi 구하는 것도 있는데 문법기억안나네

//mask 사이즈는 무조건 5다.
// ans 사이즈와 mask 사이즈는 다른거다. 즉 m이 무조건 5가 아니라는 것이다.

//1~n까지 조합을 통해 mask 배열이 완성되면
//q의 각 원소배열의 원소값들과 비교해서 일치 값 갯수가 ans와 순서가 맞는 지 체크해서
//매칭이 안되면 바로 return 후 다음 mask 만들기.
//매칭 될 경우 counting

int result = 0;
void recursion(vector<int>&mask, const int n, const vector<vector<int>> &q, const vector<int> &ans, int lv, int num)
{
    if (lv == 5) {
        for (int z = 0; z < q.size(); ++z) {
            int cnt = 0;
            for (int y = 0; y < q[z].size(); ++y) {
                for (int x = 0; x < mask.size(); ++x) { // 조합된 마스크 배열과 q의 원소배열의 원소 값 비교
                    if (mask[x] == q[z][y]) {
                        cnt++;
                    }
                }
            }
            if (ans[z] != cnt) // 언매칭에 따른 다른 마스크 조합으로 넘어가는 가지치기
            {
                return;
            }
        }
        result++;
        return;
    }
    for (int val = num; val <= n; ++val) { // num은 1부터 시작
        mask[lv] = val;
        recursion(mask, n, q, ans, lv + 1, val + 1); // num +1이 n 초과시 for문은 자동으로 걸러질거임.
    }

}
int solution(int n, vector<vector<int>> q, vector<int> ans) {
    vector<int>mask(5, 0);
    recursion(mask, n, q, ans, 0, 1); // num은 1부터 시작 1~n까지이니
    return result;
}

 

 

2. todo: permutation 문법이 있어서 그거 통해서도 해결해보기