문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/42890?
카카오 코딩 테스트 문제 위주로 풀고 있는데,
어째 Level 2에 나오는 문제는 왜 전부 유형이 비슷한 거 같지?
문제 핵심 및 풀이
제한 사항 부분에서 문제의 유형을 알 수 있다.
고를 수 있는 선택지인 column이 최대 8개,
판별해야 할 row는 최대 20밖에 되지 않는다.
탐색 범위가 엄청 작은 것을 알 수 있어서,
이 문제는 완전 탐색으로 충분히 풀 수 있다는 것을 알 수 있다.
키 쌍이 될 수 있는 경우의 수
어떤 속성(column)의 조합이 후보키가 될 수 있는지는
속성 조합을 만들어보고, 직접 모든 row와 비교해 보는 수밖에 없다.
그렇기 때문에 결국엔 조합이 될 수 있는 모든 경우를 고려해야 한다.
column 수에 대해 모든 조합을 백트래킹을 통해 구한다.
이때, 같은 속성은 한 번만 쓰일 수 있고 순서 또한 존재하지 않는다.
그러니까 사용하는 column 번호를 인덱스로 뒀을 때
(1,1) 이런 중복도 안되고, (1,3)이나 (3,1)이나 같은 키 쌍이라는 것이다.
그렇기 때문에 백트래킹을 할 때, 중복되지 않는 조합이라는 것을 명심하면서 백트래킹을 돌린다.
유일성을 만족하는지 확인
결국 해당 키 쌍이 모든 것을 구분할 수 있는지를 확인해야 한다.
그리고 모든 rows는 문자열로 이루어진 상태이다.
각 row에서 해당 키 쌍, 즉 속성만 뽑아낸다.
그리고 그 문자열로 이루어진 리스트가 다른 row에서도 존재하는지 확인한다.
최소성 만족하는지 확인
최소성을 확인하기 위해 현재 검사 중인 키 쌍 안에
앞서 구해놨던 후보키가 속해있는지 검사해야 한다.
예를 들어 후보키에 (1,2)가 들어있다.
그러면 (1,2,3) 키 쌍 안에는 무조건 (1,2)가 들어있기 때문에
(1,2,3) 키 쌍은 최소성을 만족시키지 않는다.
이 점을 위해서라도 키 쌍의 개수가 작은 것부터 검사해야 한다.
그러니까 키 쌍이 1개를 다 끝내고
2개.. 3개인 것 이런 식으로 검사해야 한다.
만약 (1,2,3)을 후보키로 등록해 두면,
(1,2)도 후보키로 등록되고 해서 (1,2,3)이 최소성을 만족시키지 않는다는 것을 알 수 없다.
실수하기 쉬운 부분
최소성의 의미 파악
이 문제에서는 유일성과 최소성이라는 2개의 키워드가 나오는데,
여기서 최소성의 의미를 이해하는 것이 중요하다.
간단한 예를 들어 설명하면,
후보키에 (1)이 있다면, (1,2) , (1,3), (1,2,3) 등은 최소성을 만족하지 않는다.
왜냐하면 (1)만 가지고도 충분히 판별이 가능하기 때문에,
다른 2와 3을 사용하는 것은 필요 없기 때문이다.
키 쌍의 문자열 구분
해당 키쌍으로 이루어진 row의 집합을
속성 문자열로 다 이어 붙인다면, 문제가 생긴다.
[["a", "aaaa"], ["aa", "aaa"]]이라고 해보자.
만약 모든 속성을 쓰는 키쌍이 있다고 하고,
이를 문자열을 이어 붙이는 방식으로 저장한다고 해보자.
그럼 실제로는 유일성을 만족하는데,
"aaaaa"가 중복되어 유일성을 불만족시키는 것으로 보인다.
그래서 이 방식을 사용하려면 중간에 구분자까지 넣어서 저장해야 한다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
vector<vector<string>> relations; // relation을 전역변수로
vector<vector<int>> keyList; // 구한 후보키의 리스트
// 유일성 만족을 확인하는 함수
bool isOverlap(vector<vector<string>> list, vector<string> cnt){
for(auto keys : list){
bool flag = true;
for(int i = 0; i < keys.size(); i++){
if(keys[i] != cnt[i]){
flag = false;
break;
}
}
if(flag) return true;
}
return false;
}
// 해당 키-쌍 값이 후보키로 등록될 수 있는지 확인
void getPossible(vector<int> keys){
vector<vector<string>> list; // 각 row 별 키 쌍 문자열 저장
// 모든 rows 순회
for(auto info : relations){
vector<string> tmp; // 해당 rows의 키쌍 문자열 저장
for(auto idx : keys) tmp.push_back(info[idx]);
// 유일성 만족 확인
if(isOverlap(list,tmp)) return;
list.push_back(tmp); // 만족하면 list에 추가
}
// 해당 키쌍이 최소성을 만족하는지 확인
for(auto keyword : keyList){
bool check = true;
// 후보키에 등록되어 있는 키쌍이 현재 키쌍에 포함되어있는지 확인
for(auto it : keyword){
auto iter = find(keys.begin(),keys.end(),it);
if(iter == keys.end()) {
check = false;
break;
}
}
if(check) return;
}
keyList.push_back(keys); // 후보키에 추가
}
// 가능한 모든 키 쌍을 구하는 함수(count = 포함할 속성의 수)
void getOrders(vector<int> keys, int cnt, int count){
if(keys.size() >= count){
getPossible(keys);
return;
}
for(int i = cnt; i < relations[0].size(); i++){
keys.push_back(i);
getOrders(keys,i+1,count);
keys.pop_back();
}
}
int solution(vector<vector<string>> relation) {
relations = relation;
vector<int> tmp;
// 최소성을 위해서 키쌍 개수가 1인 것부터 시작해야함
for(int i = 1; i <= relation[0].size(); i++) getOrders(tmp,0,i);
int answer = keyList.size(); // 구해둔 모든 후보키의 개수
return answer;
}↑
Java 구현 코드
↓
import java.util.*;
import java.util.stream.*;
class Solution {
public String[][] relation; // relation을 전역 변수로
public List<List<Integer>> keyList = new ArrayList<>(); // 구한 후보키 리스트
// 나올 수 있는 모든 키쌍을 구함(count = 키쌍에 포함될 속성의 개수)
public void getOrders(List<Integer> keys, int cnt, int count){
if(keys.size() >= count){
System.out.println(keys);
Collections.sort(keys);
isPossible(new ArrayList<Integer>(keys));
return;
}
for(int i = cnt; i < relation[0].length; i++){
List<Integer> tmp = new ArrayList<>(keys);
tmp.add(i);
getOrders(tmp,i+1,count);
}
}
// 해당 키쌍이 후보키가 될 수 있는지 확인하는 함수
public void isPossible(List<Integer> keys){
List<List<String>> list = new ArrayList<>(); // 각 rows에서 키-쌍의 문자열 리스트
// 모든 rows를 순회
for(String[] info : relation){
List<String> tmp = new ArrayList<>(); // 해당 rows의 키쌍 문자열 리스트
for(int idx : keys) tmp.add(info[idx]);
// 유일성을 만족하는지 확인하는 check 함수 호출
if(list.stream().anyMatch(e -> check(e,tmp))) return;
list.add(tmp);
}
// 최소성을 만족하는지 확인
for(List<Integer> keyword : keyList){
if(keyword.stream().allMatch(e -> keys.contains(e) == true)) return;
}
keyList.add(keys); // 다 만족하면 keyList에 추가
}
// 유일성을 만족하는지 확인(list : 후보키 , target: 비교할 문자열 리스트)
public boolean check(List<String> list, List<String> target){
for(int i = 0; i < target.size(); i++){
if(!target.get(i).equals(list.get(i))) return false;
}
return true;
}
public int solution(String[][] relation) {
this.relation = relation;
// 최소성을 위해 먼저 1개부터 시작
for(int i = 1; i <= relation[0].length; i++)
getOrders(new ArrayList<Integer>(),0,i);
int answer = keyList.size();
return answer;
}
}↑
시행착오
최소성을 만족하는 조건을 찾는 것이 어려웠고, 최소성 자체를 이해하는데도 어려웠다.
시간제한을 두고 풀었을 때, 못 풀었다.
처음에는 Map 자료구조를 사용했는데, 그럴 필요가 없다는 것을 알았다.
그런데 string으로 하는 것도 좀 걸리더라
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me