[프로그래머스] 2019 KAKAO BLIND RECRUITMENT 후보키 with Kotlin

문제

출처 프로그래머스

위와 같이 2차원 배열로 DB가 주어졌을때, 후보키의 개수를 구하는 문제

 

후보키란?

• 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
  • 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
  • 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

즉, 각 행이 중복되지 않고 최소한의 속성만 갖고 있을 때 해당 속성들을 후보키라고 한다.

 

예를 들어

1. 학번은 중복되지 않음으로 후보키다.

2. 이름 + 전공 또한 중복되지 않고 어느 한 속성을 뺄 수 없기에 최소성도 만족하여 후보키다.

3. 이름 + 전공 + 학년은 중복되진 않지만 학년을 빼도 후보키가 가능함으로 최소성을 만족하지 못한다.

 

풀이 과정

1. 유일성을 만족하는 단일 속성을 찾고, 유일성을 만족하지 못하는 속성들로 조합하여 확인

2. 유일성을 만족하지 못하는 속성들로 모든 조합을 찾아야하기 때문에 BFS로 진행

3. 속성들의 조합 중 최소성을 만족하지 못하는 조합 제거

• 만약 인덱스 (1, 3) 속성이 후보키라면, 3가지 속성의 조합에서 (1, 3)이 포함되어 있다면 최소성을 만족하지 못한다.   

* 이건 개인적인 풀이과정 입니다.

 

 

추가 테스트케이스

relation	return
[["a", "1", "aaa", "c", "ng"], ["a", "1", "bbb", "e", "g"], ["c", "1", "aaa", "d", "ng"], ["d", "2", "bbb", "d", "ng"]]	5

 

 

 

코드

import java.util.*
class Solution {
    //1. 중복되는 행이 없는 열
    //2. 중복되는 행이 있는 열의 조합 중 중복이 없는 것
    
    fun solution(relation: Array<Array<String>>): Int {
        // 후보키가 아닌 조합 모음
        val queue: Queue<MutableList<Int>> = LinkedList<MutableList<Int>>()
        // 후보키 저장 
        val candidateKey = mutableListOf<MutableList<Int>>()
        
        // x : 행 , y : 열
        // 1. 중복없는 행을 가진 열 찾기
        for(y in relation[0].indices){
            val setList = mutableSetOf<String>()
            for(x in relation.indices){
                setList.add(relation[x][y])
            }
            
            // 중복 없는 행 -> 후보 키
            if(setList.size == relation.size) candidateKey.add(arrayListOf(y))
            else queue.add(arrayListOf(y)) // 중복 있는 행
        }

        // 2. 속성들의 조합 확인 (BFS)
        while(queue.isNotEmpty()){
            val q = CandidateKey(queue.poll())
            // 1차 최소성 확인
            if(candidateKey.contains(q.list)) continue
            
            // q가 [1]이면 인덱스 2부터 조합
            for(y in q.list[q.list.size-1]+1 until relation[0].size){
                // 2차 최소성 확인
                if(candidateKey.contains(arrayListOf(y))) continue
                val setList2 = mutableSetOf<MutableList<String>>()
                
                // 유일성 확인
                for(x in relation.indices){
                    val list = mutableListOf<String>()
                    q.list.forEach{
                        list.add(relation[x][it])
                    }
                    list.add(relation[x][y])
                    
                    setList2.add(list)    
                }   
                
                // q 깊은 복사 후 추가
                val newList = q.copy()
                newList.list.add(y)
                
                // 중복이 없다면 후보키에 추가
                if(setList2.size == relation.size) {
                    
                    // 3차 최소성 확인
                    var duplicate = false
                    for(i in candidateKey){ 
                        var boolean = true
                        val delete = newList.copy() 
                        i.forEach{ it ->
                            val index = delete.list.indexOf(it)
                            // 중복X
                            if(index == -1) boolean = false
                        }
                        
                        if(boolean){ 
                            duplicate = true
                            break
                        }
                    }
                    
                    if(duplicate) continue
                    
                    candidateKey.add(newList.list)
                }
                // 중복이라면 queue에 추가
                else queue.add(newList.list) 
            }
        }
        
        return candidateKey.size
    }
    
    // list 깊은 복사를 위해
    data class CandidateKey(
        val list: MutableList<Int>
    ){
        fun copy(): CandidateKey {
            return CandidateKey(list.toMutableList())
        }
    }
}