1. 문제 및 예제
이건 입력되는 데이터의 최대값만 봐도 전부 돌리는 Brute force라는 것을 알았다. DFS와 조합 중에 고민하였는데 이는 사치라는 생각을 깨닫고 조금 더 빠르게 구현할 수 있도록 재귀 함수를 사용해 조합을 구현해보았다.
최대의 후보키를 구하는 문제여서 햇갈릴 수 있는데 속성이 작은 쪽부터 순차적으로 올라간다면 이 부분은 해결된다. 카카오의 문제들은 항상 높은 집중력을 요한다... 구현 문제를 기본적으로 효율적이게 접근할 수 있는 사람이 유리할 것 같다.
https://school.programmers.co.kr/learn/courses/30/lessons/42890
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
2. 풀이과정
문제를 나눠보았다.
1. 후보키의 예상 갯수 만큼 for문 진행.
- 예를 들어 속성(col)의 전체 값이 5라면 1개의 속성을 가지는 후보키 부터 5개의 속성을 가지는 후보키까지 존재할 수 있기 때문에, 1부터 5까지 for문을 진행한다.
2. 후보키의 갯수만큼 나올 수 있는 모든 조합을 구한다.
- 예를 들어 5개의 속성 갯수 중 기준 수가 2라면 나올 수 있는 모든 경우의 수인 5 * 4 = 20 만큼의 모든 조합을 계산한다.
3. 구해진 후보키에 대해서 모든 튜플을 구분할 수 없다면 answers set에 추가한다.
4. answers의 갯수를 return한다.
- get_cols()
해당 함수는 모든 경우의 수를 구하는 재귀함수이다. 속성이 3개이고 이중 2개의 키를 조합하는 경우의 수를 배열에 추가해준다. 다음과 같을 것이다.
[ (1,2), (1,3), (2,3) ]
다음은 함수의 코드이다.
void get_cols(int max, int count, int start, int size) {
if (count < max) {
for (int i = start; i < size; i++) {
if (!visited[i]) {
visited[i] = true;
get_cols(max, count + 1, i + 1, size);
visited[i] = false;
}
}
}
else {
vector<int> tmp;
for (int i = 0; i < size; i++) {
if (visited[i]) {
tmp.push_back(i);
}
}
keys.push_back(tmp);
}
}
- find_str()
해당 함수는 최소성을 고려한 함수이다. 만약 2,3을 조함한 후보키가 있다고 가정했을 때 이미 2를 후보키로 가지고 있다고 하면 2와 3을 조합한 후보키는 최소성을 가지지 못한다.
그러나 또 단순하게 find() 를 사용하면 안된다. 예를 들어 "14"를 조합한 후보키가 있을 때, "124"는 최소성을 가지지 못하지만, "124".find("14")는 npos를 반환한다. 따라서 "14"를 이루는 모든 숫자 즉 1과 4 전부 "124"안에 있는지를 판단해야한다. 다음은 함수 코드이다.
bool find_str(string str) {
for (auto key : answers) {
int count = 0;
for (auto it : key) {
if (str.find(it) != string::npos)
count++;
}
if (count == key.size())
return false;
}
return true;
}
- 전체 코드
다음은 전체 코드이다.
#include <string>
#include <vector>
#include <set>
using namespace std;
bool visited[8] = { 0 };
set<string> answers;
vector<vector<int>> keys;
bool find_str(string str) {
for (auto key : answers) {
int count = 0;
for (auto it : key) {
if (str.find(it) != string::npos)
count++;
}
if (count == key.size())
return false;
}
return true;
}
void get_cols(int max, int count, int start, int size) {
if (count < max) {
for (int i = start; i < size; i++) {
if (!visited[i]) {
visited[i] = true;
get_cols(max, count + 1, i + 1, size);
visited[i] = false;
}
}
}
else {
vector<int> tmp;
for (int i = 0; i < size; i++) {
if (visited[i]) {
tmp.push_back(i);
}
}
keys.push_back(tmp);
}
}
void is_key(vector<vector<string>> relation) {
for (auto cols : keys) {
set<string> all_key;
bool dir = true;
for (int row = 0; row < relation.size(); row++) {
string tmp;
for (int i = 0; i < cols.size(); i++) {
tmp += relation[row][cols[i]];
}
if (all_key.find(tmp) == all_key.end()) {
all_key.insert(tmp);
}
else {
dir = false;
}
}
if (dir) {
string key_str;
for (int i = 0; i < cols.size(); i++) {
key_str += to_string(cols[i]);
}
if (find_str(key_str)) {
answers.insert(key_str);
}
}
}
}
int solution(vector<vector<string>> relation) {
for (int i = 1; i <= relation[0].size(); i++) {
for (int j = 0; j < 8; j++) {
visited[j] = false;
}
keys.clear();
get_cols(i, 0, 0, relation[0].size());
is_key(relation);
}
return answers.size();
}
3. 결어
첫 설계로 풀기까지 약 40분 그러나 이 방법에서 오류가 나니까 바로 엄청난 시간이 들었다.. 역시 이런 복잡한 구현문제는 설계부분부터 확실하게 잡고 들어가는 것을 연습해야겠다.