[카카오 기출/Kotlin] 후보키

문제

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

풀이 흐름

1. 후보 키 목록 뽑기 -> 비트 연산을 활용한 조합구하기
2. 최소성 검사 -> 비트 연산 활용
3. 유일성 검사 -> 자료구조 Set 활용
   • 후보키 에 속하는 속성을 String으로 이어붙인 뒤 set에 넣어주기
   • ex) 후보키가 이름, 전공 이렇게 두가지가 있다면 아래와 같이 처리함
     val hashSet = {"ryanmusic, "apeachmath" .. }

조합에 관해 느낀점

c++에서는 조합을 구할 때 algorithm STL에서 지원해주는 permutation 함수를 활용해 편리하게 구현했었다.

그런데 kotlin에서는 조합 합수의 경우 재귀함수로 구성하는 등 그 과정이 좀 복잡하게 느껴졌는데 비트 연산을 활용하면 된다.

해당 문제에서 주어진 테스트 케이스의 경우 컬럼이 4였다. 그러면 후보키 조합이 2 x 2 x 2 x 2 이렇게 총 16가지가 있다

이는 아래와 같이 2진수로 표현할 수 있다.

10진수	2진수	bitCount
0	0000	0
1	0001	1
2	0010	1
3	0011	2
4	0100	1
5	0101	2
6	0110	2
7	0111	3
8	1000	1
9	1001	2
10	1010	2
11	1011	3
12	1100	2
13	1101	3
14	1110	3
15	1111	4

풀이과정 Idea

1. 유일성을 충족하기 위해, 후보키 목록을 뽑은 다음, 후보키의 개수가 작은것부터 검사해야한다.
   • 10진수로 조합을 설정한 뒤, bitCount와 sortedBy 함수를 활용해 정렬한다

   // 주어진 테케의 경우 combination num은 2^n 인 16
   val sortedNumbers = (1 until combinationNum) 
       .sortedBy { Integer.bitCount(it) }

2. 최소성 검사
   • number의 조합에 이미 후보키가 된것이 포함돼있다면 해당 조합은 후보키로 사용할 수 없음 (∵ 최소성 미충족)
3. val candidates = mutableListOf<Int>() for (number in sortedNumbers) { // 최소성 검사 var isPossible = true for (candidate in candidates) { if ((number and candidate) == candidate) { // 비트마스킹 isPossible = false break } } if (!isPossible) continue // 이후 유일성 검사 }
4. 유일성 검사
   1. 10진수 -> 2진수 String으로 표현
   2. toString(진수)
   3. ex) 10진수 9라면 101(2) 로 표현
   4. padStart(몇자리 수를, 어떤 char로 채워넣을거다) -> padStart( n, '0')
   5. ex) padStart가 중요한 이유는, 몇번째 index에 있는것이 후보키로 활용될것인가를 파악해야하기 때문

   val set = hashSetOf<String>()
   
   for (i in 0 until row) { // 가로 한줄씩 검사
       val r = relation[i]
       var string = ""
       val binary = number.toString(2).padStart(column, '0') // 2진수 변환 string
       binary.mapIndexed { idx, it ->
           if (it == '1') string += r[idx]
       }
       if (set.contains(string)) {
           break
       } else {
           set.add(string)
       }
   }
   
   if (set.size == row) {
       println(number)
       candidates.add(number)
   }

 

 

## 전체코드 

```kotlin

package programmers.kakao19

import kotlin.math.pow

class Candidate {
    fun solution(relation: Array<Array<String>>): Int {

        val row = relation.size
        val column = relation[0].size
        val combinationNum = 2.0.pow(column).toInt()

        // 후보키 목록 뽑은 다음 size가 작은것부터 정렬
        val sortedNumbers = (1 until combinationNum)
            .sortedBy { Integer.bitCount(it) }

        val candidates = mutableListOf<Int>()

        for (number in sortedNumbers) {
            // 최소성 검사
            var isPossible = true
            for (candidate in candidates) {
                if ((number and candidate) == candidate) {
                    isPossible = false
                    break
                }
            }
            if (!isPossible) continue


            val set = hashSetOf<String>() // 유일성 검사

            for (i in 0 until row) { // 가로 한줄씩 검사
                val r = relation[i]
                var string = ""
                val binary = number.toString(2).padStart(column, '0') // 2진수 변환 string
                binary.mapIndexed { idx, it ->
                    if (it == '1') string += r[idx]
                }
                if (set.contains(string)) {
                    break
                } else {
                    set.add(string)
                }
            }
            if (set.size == row) {
                println(number)
                candidates.add(number)
            }
        }
        println(candidates.size)
        return candidates.size
    }
}

fun main() {

    val relation =
        arrayOf(
            arrayOf("100", "ryan", "music", "2", "0"),
            arrayOf("200", "apeach", "math", "2", "1"),
            arrayOf("300", "tube", "computer", "3", "2"),
            arrayOf("400", "con", "computer", "4", "3"),
            arrayOf("500", "muzi", "music", "3", "4"),
            arrayOf("600", "apeach", "music", "2", "5")
        )
    Candidate().solution(relation)
}