반응형
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- Docker
- softeer
- 13908
- compose
- dfs
- 성적평가
- 기술면접
- 연결요소
- 6987
- 퇴사통보
- boj #19237 #어른 상어
- 백트래킹
- 오퍼레터
- 물채우기
- 백준
- 처우협의
- 이분탐색
- 소프티어
- 처우산정
- 경력
- 매개변수탐색
- 파라메트릭
- BOJ
- @P0
- upper_bound
- OFFSET
- incr
- BFS
- msSQL
- Kafka
Archives
- Today
- Total
기술 블로그
후보키 본문
728x90
반응형
https://programmers.co.kr/learn/courses/30/lessons/42890
백트래킹을 실행하면
1 2 3
1 3
2 3
이런 식으로 vv 벡터에 저장되고
이것을
1 3
2 3
1 2 3
sort를 통해 위처럼 바꿔줘야 한다. (짧은 것이 우선이므로)
그 다음
1 2 3 안에 1 3이 포함되었는지 검사해야 한다.
그리고 answer을 증가시키면 안 되므로,
visit 배열을 통해 탈락된 배열의 인덱스 번호에 대하여 방문 여부를 처리하여 answer을 셈한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 | #include <bits/stdc++.h> using namespace std; bool c[10]; int answer = 0; vector<int> v; bool visit[100100]; vector< pair<int, vector<int> > > vv; void backtracking(vector<int> vc, int idx, vector<vector<string> > relation) { if (vc.size() >= 2) { map<string, int> m; bool stop = true; for (int i = 0; i < relation.size(); i++) { string k = ""; for (auto j : vc) k += relation.at(i).at(j); if (m.count(k)) { stop = false; break; } m[k] = 1; } if (stop) { vv.push_back({vc.size(), vc}); return; } } for (int i = idx; i < v.size(); i++) { vc.push_back(v.at(i)); backtracking(vc, i + 1, relation); vc.pop_back(); } } bool chk(vector<int> S, vector<int> B) { int cnt = 0; for (auto i : S) for (auto j : B) if (i == j) { ++cnt; break; } if (cnt == S.size()) return false; return true; } int solution(vector<vector<string>> relation) { // 1개 for (int i = 0; i < relation.at(0).size(); i++) { bool go = true; map<string, int> m; for (auto row : relation) { if (m.count(row.at(i))) { go = false; break; } else m[row.at(i)] = 1; } if (go) { c[i] = true; ++answer; } } for (int i = 0; i < relation.at(0).size(); i++) if (!c[i]) v.push_back(i); vector<int> vc; backtracking(vc, 0, relation); sort(vv.begin(), vv.end()); for (int i = 0; i < vv.size(); i++) { if (visit[i]) continue; ++answer; for (int j = i + 1; j < vv.size(); j++) if (!chk(vv.at(i).second, vv.at(j).second)) visit[j] = true; } return answer; } int main(void) { /*vector<vector<string> > vs = { {"100", "ryan", "music", "2"}, {"200", "apeach", "math", "2"}, {"300", "tube", "computer", "3"}, {"400", "con", "computer", "4"}, {"500", "muzi", "music", "3"}, {"600", "apeach", "music", "2"} };*/ vector<vector<string> > vs = { { "a", "A", "1", "4" }, { "b", "B", "2", "4" }, { "c", "A", "1", "6" } }; printf("%d\n", solution(vs)); return 0; } | cs |
728x90
반응형