프로그래머스 - Lv2. 후보키 Kotlin

프로그래머스

프로그래머스의 후보키 문제입니다.

2레벨 문제예요.

만만히 봤다가 블로그에 알고리즘 문제 풀이 카테고리를 만들게 되었습니다.

하...

문제 설명

프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.

그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.

후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.

관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.

• 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
• 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

제이지를 위해, 아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.

입출력 예 #1

위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 "학번"을 가지고 있다. 따라서 "학번"은 릴레이션의 후보 키가 될 수 있다.

그다음 "이름"에 대해서는 같은 이름("apeach")을 사용하는 학생이 있기 때문에, "이름"은 후보 키가 될 수 없다. 그러나, 만약 ["이름", "전공"]을 함께 사용한다면 릴레이션의 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다.

물론 ["이름", "전공", "학년"]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다.

따라서, 위의 학생 인적사항의 후보키는 "학번", ["이름", "전공"] 두 개가 된다.

릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.

제한사항

• relation은 2차원 문자열 배열이다.
• relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
• relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
• relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
• relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

---

 

 

생각 흐름

 

첫 번째 시도

처음에는 dfs로 속성의 조합을 전부 구하고, 모든 dfs 호출 시 식별 함수를 따로 두어서 조건을 만족하는 조합의 개수를 세 주면 되겠다고 생각했어요.

그리고 속성의 visited 배열을 만들어서 모든 속성에 방문하고 나면 종료되도록 구현했습니다.

여기에서 하나 틀렸습니다.

설계는 맞았는데 조합이 아니라 순열을 구하도록 구현했어요.

순열
서로 다른 n개 중 r개를 선택하는 경우의 수. 순서를 고려한다.

조합
서로 다른 n개 중 r개를 선택하는 경우의 수. 순서를 고려하지 않는다.

코드를 잠깐 볼까요.

아래는 처음 구현했던 dfs 함수입니다.

fun dfs(visited: BooleanArray) {
	if (checkCandidateKey(visited)) {
		answer++
		return
	}

	for (i in visited.indices) {
		if (!visited[i]) {
			visited[i] = true
			dfs(visited, i)
			visited[i] = false
		}
	}
}

뭔가 이상하죠?

for문 내부에서 visited 배열로 방문체크만 해주고 있습니다.

이러면 어떻게 되느냐.

visited[1] = true, visited[3] = true

이 경우와

visited[3] = true, visited[1] = true

이 경우가 다르게 카운트됩니다. 즉, 순열을 구한 꼴이죠.

하...

입출력 예시 기댓값이 2인데 43을 뱉더라고요.

입출력 예시부터 틀려서 로직이 틀렸나 싶었습니다.

그래서 두 번째 시도는 유니온 파인드로 했습니다.

제가 왜 그랬을까요?

여기서 시작된 스노우볼 덕분에 3차까지 굴러갑니다.

 

두 번째 시도

이렇게 생각한 이유가 있습니다.

입출력 예제 1번 조합이 인덱스로 나눠 보면 { 0 }, { 1, 2 } 였거든요.

앗 이거 disjoint set인가? 그럼 union-find를 써야 하나?

그래서 class 만들기는 좀 오버헤드니까 parent IntArray를 만들어서 여기에 top node index를 저장할까~

했습니다.

다행히도 금방 정신 차리고 구현은 하지 않았습니다.

왜냐하면 이렇게 하면 키 하나가 여러 조합에 사용될 때 올바르게 판별할 수 없습니다.

예제 1번에서 마지막 줄의 학생의 전공을 computer로 바꿔 봅시다.

입출력 예 #1

그럼 식별 가능한 속성 조합이

1. 학번
2. 이름 & 전공
3. 전공 & 학년

총 3가지가 된다는 것을 알 수 있습니다.

여기서 전공은 두 번 사용되는 것도 보이죠.

그래서 disjoint set으로 풀 수 없습니다.

 

세 번째 시도 - 성공!

정신을 차리고 첫 번째 시도의 로직이 맞다고 확신하게 되었어요.

그런데도 틀린 이유는 제 허접한 실력 때문이었습니다.

아래는 올바른 체크 함수 코드입니다.

dfs 호출 시마다 호출되며 visited 배열로 만들어진 조합이 문제 조건에 맞는지 검사해 주는 함수예요.

fun checkCandidateKey(visited: BooleanArray): Boolean {
	var keys = relation.map { it.filterIndexed { index, _ -> visited[index] } }
	
	// isUnique
	for (key in keys) {
		if (keys.count { it == key } != 1)
			return false
	}

	// isMinimal
	if (visited.count { it } == 1) return true

	var count = 0
	for (i in 0 until keys[0].size) {
		var testKeys = keys.map { it.filterIndexed { index, _ -> index != i } }
		for (key in testKeys) {
			if (testKeys.count { it == key } != 1) {
				count++
				break
			}
		}
	}
}

 

1. array.count() 사용 미스

코드를 보시면 array.count() 함수를 꽤 자주 호출하고 있는 것을 볼 수 있습니다.

for문 늘리기 싫어서 함수 호출을 해 주었어요.

저걸 잘못 썼습니다.

 if (visited.count { true } == 1)

이게 뭘까요?

count()는 { } 내부의 람다식이 true일 때의 개수를 리턴해 줍니다.

맞습니다...

위의 코드는 visited 배열의 사이즈를 리턴합니다.

true인 원소의 개수를 리턴하는 것이 아니라요...

 

2. Kotlin의 equals(), ==, ===

java의 ==는 primitive type의 경우 값을 비교하고, reference type의 경우 주소를 비교합니다.

물론 엄밀하게 말하자면 primitive type의 경우에도 Constance Pool에 존재하는 특정 상수의 주소값을 비교하는 거니까 정확한 value를 비교하는 것은 아닙니다.

아무튼 객체가 들어오면 객체의 주소값을 비교합니다.

이때 객체의 주소값이 같으면 true를 반환하는데, 그냥 같은 객체라는 뜻이죠.

이걸 동일성이라고 합니다.

이때 객체의 값을 비교하기 위해서는 일반적으로 equals()를 사용하는데요.

"일반적인" String 객체의 경우 eqauls()가 미리 오버라이딩되어 있습니다.

그래서 주소값이 아니라 값 비교를 해 줍니다.

주소값이 달라도 값은 동일할 수 있죠.

이걸 동등성이라고 합니다.

동일성 identity
동일하다는 뜻으로, 두 개의 객체가 완전히 같은 경우를 뜻한다.
주소값이 같다.

동등성 equality
동등하다는 뜻으로, 두 개의 객체가 동등한 정보를 가진 경우를 뜻한다.
주소값이 달라도 값은 동일할 수 있으므로, 동일성이 성립하지 않더라도 동등성이 성립할 수 있다.

다른 객체는 경우에 따라 다르고 원하는 동작을 하지 않을 수도 있어서 필요할 경우 사용자가 직접 오버라이딩해야 합니다.

아주 불친절하죠?

그러나 Kotlin은 다릅니다.

---

Kotlin은 == 연산자가 equals()입니다.

즉 동등성을 검사합니다.

공식 문서에서 친절하게 설명해주고 있습니다. 헷갈리는 사람이 얼마나 많았길래...

Equality | Kotlin

그런데 이걸 본 후에도 이게 맞나 싶은 부분이 있었습니다.

// isUnique 주석 밑의 for문을 보시면 내부에서 count() 를 사용해서 원소 개수를 세고 있는 것을 보실 수 있는데요.

이 부분입니다.

// isUnique
	for (key in keys) {
		if (keys.count { it == key } != 1)
			return false
	}

그런데 이 람다식에서 it과 key의 type은 List<String>입니다.

킹갓 Kotlin이 list의 내부 원소까지 들여다보면서 동등성 체크를 해 주는 걸까요?

놀랍게도 맞습니다.

equals - Kotlin Programming Language

공식문서 list.equals() 설명

해석해 드릴게요.

파라미터로 들어온 인스턴스가 "똑같은 사이즈"이고, "똑같은 원소"를 "똑같은 순서"로 가진 리스트라면 return true

입니다.

그래서 단 4줄만으로 가독성 끝내주는 for문이 완성됩니다. 더 줄이면 무려 3줄이에요.

짱이야!

저는 선언형이 너무 좋아요.

아무튼 얘는 대충 짰는데 얼떨결에 잘 돌아가길래 엥 왜 돌아가지 싶어서 알아본 내용입니다.

맞았지만 궁금했어요.

 

3. 유일성 검사

윗윗 코드의 // isMinimal 주석을 달아준 파트에서 유일성 검사를 하는데요.

아래와 같은 코드입니다.

// isMinimal
	if (visited.count { it } == 1) return true

	var count = 0
	for (i in 0 until keys[0].size) {
		var testKeys = keys.map { it.filterIndexed { index, _ -> index != i } }
		for (key in testKeys) {
			if (testKeys.count { it == key } != 1) {
				count++
				break
			}
		}
	}

이 유일성 검사는 어떻게 돌아가야 하냐면, 모든 원소가 "조합에서 빠지면 후보키가 될 수 없는 원소"여야 합니다.

그래서 원소가 더 빠질 수 없는 조합, 즉 원소 1개짜리 조합일 때는 그대로 리턴해 주었고요.

그 이상일 때는 count 변수를 두었습니다.

for문 내부의 testKeys는 반복문이 돌 때마다 "원래 조합"에서 모든 속성을 하나씩 빼서 새롭게 만든 데이터입니다.

이렇게 만들어진 데이터는 당연히 식별되면 안 됩니다.

즉, 식별이 되지 않는다면 올바른 조합입니다.

그러니까 모든 속성을 하나씩 빼서 전부 테스트를 했을 때 제대로 식별되는 경우가 하나라도 있으면 안 되는 것이죠.

for문을 다 돌았을 때 count의 값이 visited 배열의 값이 true인 원소의 개수와 동일하면 모든 검사가 잘 끝난 겁니다.

 

4. 순열 & 조합

아까 1차 시도에서 순열 & 조합을 잘못 구현했었죠.

목표는 조합입니다.

그래서 순서를 신경 써 줍니다.

fun dfs(visited: BooleanArray, now: Int) {
    if (checkCandidateKey(visited)) {
        answer++
        return
    }
    for (i in visited.indices) {
        if (!visited[i] && now <= i) {
            visited[i] = true
            dfs(visited, i)
            visited[i] = false
        }
    }
}

dfs 함수에 now라는 변수를 추가해서 현재 어떤 인덱스를 방문했는지 기록해 주었습니다.

그리고 if문에 조건을 하나 더 넣어 주었어요.

now <= i 입니다.

이 조건을 추가해 주면 조합이 오름차순으로 하나만 세어집니다.

등호 빼면 안 됩니다.

전체 코드 보면 아시겠지만 dfs(visited, 0)로 함수를 호출하는데, 0이 now로 들어가서 영원히 false인 상태로 실행됩니다.

 

 

정답

class Solution {
    fun solution(relation: Array<Array<String>>): Int {
        
        var answer = 0
        var visited = BooleanArray(relation[0].size)

        fun checkCandidateKey(visited: BooleanArray): Boolean {
            var keys = relation.map { it.filterIndexed { index, _ -> visited[index] } }
            
            // isUnique
            for (key in keys) {
                if (keys.count { it == key } != 1) return false
            }

            // isMinimal
            if (visited.count { it } == 1) return true
            var count = 0
            for (i in 0 until keys[0].size) {
                var testKeys = keys.map { it.filterIndexed { index, _ -> index != i } }
                for (key in testKeys) {
                    if (testKeys.count { it == key } != 1) {
                        count++
                        break
                    }
                }
            }

            return count == visited.count { it }
        }

        fun dfs(visited: BooleanArray, now: Int) {
            if (checkCandidateKey(visited)) {
                answer++
                return
            }
            for (i in visited.indices) {
                if (!visited[i] && now <= i) {
                    visited[i] = true
                    dfs(visited, i)
                    visited[i] = false
                }
            }
        }

        dfs(visited, 0)
        return answer
    }
}