[JAVA] 프로그래머스 - 후보키 (feat. 이틀..)

https://programmers.co.kr/learn/courses/30/lessons/42890

코딩테스트 연습 - 후보키

이틀동안 머리를 굴려 완성한 코드,, 솔직히 인터넷에 검색하면 내가 작성한 코드보다 훨씬 좋은 방법이 많이 있을거 같았는데, 끝까지 해내고싶어서 완성한 코드이다 하하하하

정말 이 코드를 짜면서 배운점이 많다... 그래서 포스팅을 추가로 할 예정이다.!

후보키는 데이터베이스 공부할 때 배웠던 내용인데, 문제에서 제시한 조건은 다음과 같다.

1. 유일성(Uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.

2. 최소성(Minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨진다.

즉, 릴레이션의 모든 튜플을 유일하게 식별하는데 꼭 필요한 속성들로만 구성되어야 한다.

두 번째 최소성에 대해 추가로 말을 하자면, 만약 "이름"이라는 속성 하나가 후보키 조건에 부합하면, 

"이름"이 들어간 속성 조합은 후보키가 되지 못한다!

.

코드는 다음과 같다.

1. 전역변수

	public static int attr_len;
	public static int tuple_len;
	public static boolean[] checked;
	public static Set<ArrayList<Integer>> key_num = new HashSet<>();
	public static String[][] rel ;

- 속성의 개수 / 튜플의 개수 / dfs에 사용할 boolean 배열 / 후보키를 저장할 hashset / 테이블 복사할 String배열

 

2. 메인 함수

	public static void main(String[] args){
		String[][] relation = {};
		
		rel = relation;
		tuple_len = relation.length;
		attr_len = relation[0].length;
		checked = new boolean[attr_len];
		dfs(0, 0, new ArrayList<Integer>());
		System.out.println(key_num.size());
	}

- relation은 문제에서 주어진 테이블(2차원 배열)으로, 다른 메소드에서 사용하기 위해 전역변수 rel에 복사한다

- 나머지 전역변수에도 각각 필요한 값을 넣어주고, dfs를 호출한다

 

3. dfs(깊이우선탐색)

public static void dfs(int dep, int idx, ArrayList<Integer> list) {
		if(dep == attr_len) {
			if(isKey(list)) {
				isKeyNum(list);
			}
			return ;
		}		
		else if(isKey(list)) {
			isKeyNum(list);
		}
			
		
		for(int i=idx; i<attr_len; i++) {
			if(!checked[i]) {
				checked[i]=true;
				list.add(i);
				dfs(dep+1, i, list);
				list.remove(list.size()-1);
				checked[i]=false;
			}
		}
		
	}

- 전에 '수식최대화' 문제에서 깊이우선탐색을 사용했을 때, 모든 조합을 탐색하는 완전 탐색 방법을 배웠기 때문에 똑같이 사용하였다

- list에 속성 인덱스를 하나씩 담아서 모든 속성조합(인덱스 값들)을 만들어낸 후, 각각 key가 될 수 있는지 먼저 판단한다(isKey)

(+ 여기서 dfs에서 idx값을 넘겨주어 중복 방지 및 인덱스 작은값~큰값 순서대로 넣음!)

- 유일성을 갖추게 된다면, 최소성을 만족하는지 확인하기 위해 또 다른 함수를 호출한다(isKeyNum)

- 두 함수 모두 해당 조합(list)을 파라미터로 넘겨준다

 

4. 유일성 확인

	public static boolean isKey(ArrayList<Integer> list) {
		ArrayList<String> arr = new ArrayList<String>();
		
		for(int i=0; i<tuple_len; i++) {
			StringBuilder sb = new StringBuilder();
			for(int j : list) {
				sb.append(rel[i][j]);
			}
			
			if(arr.contains(sb.toString()))
				return false;
			arr.add(sb.toString());
		}
		return true;
	}

- ArrayList로 넘어오기 때문에 똑같이 받아주고, 튜플 내용을 검사한다

- 튜플 내용이 모두 String으로 이루어져있기 때문에 StringBuilder를 사용하여 값을 모조리(?) 하나의 String으로 모아준다

- 그리고 미리 선언해 놓은 ArrayList<String>에 하나씩 비교하면서 넣고, 만약 중복값이 있다면 false를 바로 리턴해준다

 

5. 최소성 확인 ★

	public static void isKeyNum(ArrayList<Integer> list) {
		int list_len = list.size();
		//list의 값이 최소성을 만족하는지 확인하는 변수
		boolean flag = true;
		
		Iterator<ArrayList<Integer>> it = key_num.iterator();
		
		while(it.hasNext()) {
			ArrayList<Integer> key_arr = new ArrayList<>(it.next());
			int key_len = key_arr.size();
			
			if(key_len == list_len) {
				continue;
			}else if(key_len > list_len) {
            	//list를 분석하여 key값이 최소성을 만족하는지 확인
				boolean isContain = true;
				for(int j=0; j<list_len; j++) {
					if(!key_arr.contains(list.get(j))) {
						isContain = false;
						break;
					}
				}
				if(isContain) {
					it.remove();
				}					
			}else {		
            	//key값을 분석하여 list의 값이 최소성을 만족하는지 확인
				boolean isContain = true;
				for(int j=0; j<key_len; j++) {
					
					if(!list.contains(key_arr.get(j))) {
						isContain = false;
						break;
					}
				}
				if(isContain) {
					flag = false;
				}
			}
			
		}
        // list를 key에 넣어도 되는지 확인 후에 넣음
		if(flag) {
        	//list를 바로 넣게 되면 이전에 넣었던 값도 변하기 때문에(주소값 동일) 새로 배열 만들기!!!
			ArrayList<Integer> newAdd = new ArrayList<Integer>(list);
			key_num.add(newAdd);
		}
		return ;
	}

- Key를 담는 곳이 Set이기 때문에 중복될 일은 없지만, list로 들어오는 값이 크기가 뒤죽박죽(?)이기 때문에 전부 검토해보아야한다

 - 기존 key 배열에 들어가 있는 리스트와 새로 판단할 list의 값 중 어느것이 큰 지 모르기 때문에 경우를 나누어서 판단하였다

- ★제일중요★ isKeyNum이 호출되어 매개변수로 들어오는 list는 모두 주소값이 동일하기 때문에, 새로 ArrayList를 만들어서 keySet에 넣어야 한다!

 

6. 전체코드 

import java.util.*;

public class Solution{
	public static int attr_len;
	public static int tuple_len;
	public static boolean[] checked;
	public static Set<ArrayList<Integer>> key_num = new HashSet<>();
	public static String[][] rel ;
	
	public static void main(String[] args){
		String[][] relation = {};
		
		rel = relation;
		tuple_len = relation.length;
		attr_len = relation[0].length;
		checked = new boolean[attr_len];
		dfs(0, 0, new ArrayList<Integer>());
		System.out.println(key_num.size());
	}
	
	public static void dfs(int dep, int idx, ArrayList<Integer> list) {
		if(dep == attr_len) {
			if(isKey(list)) {
				isKeyNum(list);
			}
			return ;
		}		
		else if(isKey(list)) {
			isKeyNum(list);
		}
			
		
		for(int i=idx; i<attr_len; i++) {
			if(!checked[i]) {
				checked[i]=true;
				list.add(i);
				dfs(dep+1, i, list);
				list.remove(list.size()-1);
				checked[i]=false;
			}
		}
		
	}
	
	public static boolean isKey(ArrayList<Integer> list) {
		ArrayList<String> arr = new ArrayList<String>();
		
		for(int i=0; i<tuple_len; i++) {
			StringBuilder sb = new StringBuilder();
			for(int j : list) {
				sb.append(rel[i][j]);
			}
			
			if(arr.contains(sb.toString()))
				return false;
			arr.add(sb.toString());
		}
		return true;
	}
	
	public static void isKeyNum(ArrayList<Integer> list) {
		int list_len = list.size();
		
		boolean flag = true;
		
		Iterator<ArrayList<Integer>> it = key_num.iterator();
		
		while(it.hasNext()) {
			ArrayList<Integer> key_arr = new ArrayList<>(it.next());
			int key_len = key_arr.size();
			
			if(key_len == list_len) {
				continue;
			}else if(key_len > list_len) {
				boolean isContain = true;
				for(int j=0; j<list_len; j++) {
					if(!key_arr.contains(list.get(j))) {
						isContain = false;
						break;
					}
				}
				if(isContain) {
					it.remove();
				}					
			}else {		
				boolean isContain = true;
				for(int j=0; j<key_len; j++) {
					
					if(!list.contains(key_arr.get(j))) {
						isContain = false;
						break;
					}
				}
				if(isContain) {
					flag = false;
				}
			}
			
		}
		if(flag) {
			ArrayList<Integer> newAdd = new ArrayList<Integer>(list);
			key_num.add(newAdd);
		}
		return ;
	}
}

 

위의 내용은 다음 포스팅에 넣겠다! ~~~~~ 그래도 이틀동안 힘들었지만,,, 해내서 만족스럽다

이제 놓아줄게.. 다음에 복습할때 봐 ! 안녕^_^ 

※ 코드를 작성할때마다 느끼는 점

1. 코드 미완성 : 난 이 길이 안 맞나봐..(눈물)

2. 길고 긴 전투 끝에 성공 : ..ㅋㅋ(지침)(뿌듯)