[프로그래머스 Lv.2] 비밀 코드 해독

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

프로그래머스

 

문제에 대놓고 조합을 쓰라고 나왔다.

 

다만, 시간초과가 날까봐 처음에 망설여졌는데 30C5이면, 1억번을 넘지 않았다.

 

또한 30C5으로 고르고 나서 ans로 들어온 배열들과 비교를 해야되는데, 30C5 * 10 * log(10)을 해도 

 

142,506 * 10 * log(10)

 

이므로 1억번에 미치지 못한다.

---

풀이

• for문으로 반복문 다 돌렸다.

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

using namespace std;

int solution(int n, vector<vector<int>> q, vector<int> ans) {

    int answer = 0;
    
    for(int i=1;i<=n;i++) {
        for(int j=i+1;j<=n;j++) {
            for(int k=j+1;k<=n;k++) {
                for(int y=k+1;y<=n;y++) {
                    for(int z=y+1;z<=n;z++) {
                        int size = ans.size();
                        vector<int> cnt(size);
                        
                        for(int p=0;p<q.size();p++) {
                            for(int w=0;w<5;w++) {
                                if (q[p][w] == i) {
                                    cnt[p]++;
                                } else if (q[p][w] == j) {
                                    cnt[p]++;
                                } else if (q[p][w] == k) {
                                    cnt[p]++;
                                } else if (q[p][w] == y) {
                                    cnt[p]++;
                                } else if (q[p][w] == z) {
                                    cnt[p]++;
                                }
                            }
                        }

                        bool flag = true;
                        for(int p=0;p<q.size();p++) {
                            if (ans[p] != cnt[p]) {
                                flag = false;
                                break;
                            }
                        }
                        
                        if (flag) {
                            answer++;
                        }
                    }
                }
            }
        }
    }
    
    return answer;
}

 

5개까지라 for문을 돌려서 해도 충분했다.. [내가 읽기에]

 

물론 재귀를 이용해서도 풀 수 있다.

하지만 프로그래머스 환경에서는 전역변수를 쓰고, 하기가 조금 까다로워 for문으로 접근했다.

#include <string>
#include <vector>

using namespace std;

void go(int start, int n, vector<int>& selected, 
         vector<vector<int>>& q, vector<int>& ans, int& answer) {
    
    // 5개를 다 선택했으면 검사
    if (selected.size() == 5) {
        bool valid = true;
        for (int p = 0; p < q.size(); p++) {
            int cnt = 0;
            for (int w = 0; w < 5; w++) {
                for (int s : selected) {
                    if (q[p][w] == s) {
                        cnt++;
                        break;
                    }
                }
            }
            if (cnt != ans[p]) {
                valid = false;
                break;
            }
        }
        if (valid) answer++;
        return;
    }
    
    // start부터 n까지 하나씩 선택해보기
    for (int i = start; i <= n; i++) {
        selected.push_back(i);
        go(i + 1, n, selected, q, ans, answer);
        selected.pop_back();  // 백트래킹
    }
}

int solution(int n, vector<vector<int>> q, vector<int> ans) {
    int answer = 0;
    vector<int> selected;
    go(1, n, selected, q, ans, answer);
    return answer;
}