Programmers(KAKAO) 후보키

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

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

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

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

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

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

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

물론 [“이름”, “전공”, “학년”]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보키가 될 수 없다. 따라서 위의 학생 인적사항의 후보키는 [“학번”], [“이름”, “전공”] 두 개가 된다.

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

제한 사항

예제 입출력

relation	result
[[“100”,”ryan”,”music”,”2”],[“200”,”apeach”,”math”,”2”],[“300”,”tube”,”computer”,”3”],[“400”,”con”,”computer”,”4”],[“500”,”muzi”,”music”,”3”],[“600”,”apeach”,”music”,”2”]]	2

데이터베이스 후보키 목록들을 알고리즘으로 선별하는 문제이다.

나같은 경우 이 문제의 접근을 조합으로 접근하였다. 사실 문제를 풀 당시에 조합을 염두에 두고 접근한 것은 아니지만 구현을 하던 중 이전에 조합 문제들을 풀 때와 유사한 알고리즘으로 풀어나가는 것을 깨달았다.

사실 문제 자체를 직관적으로 해석하면 조합 문제로 접근하는 것이 가장 쉽다. 속성(컬럼) 목록들 중 후보키 자격을 갖는(유일성, 최소성) 컬럼들의 조합을 구하면 되기 때문이다.

또한 제한 사항으로 주어진 범위도 재귀와 다중 루프를 사용하는데 큰 문제가 없어보인다.

단, 요소의 개수가 정해져 있지 않고 [1개 ~ realtion 컬럼의 개수] 까지 전부 조합의 범위가 된다.

또한 후보키의 조건인 유일성, 최소성을 판별을 위한 로직까지 필요하다.

문제 해결의 절차는 다음과 같다.

조합을 응용하여 해결하는 문제로써 사실 많이 헤멘 문제이다.

가장 많이 헤맨 부분은 최소성 판별(isMinimal)을 구현하기 위해 candidateSet과 columnList에서 요소를 꺼내어 판별하는 부분이 헷갈렸다. (사실 로직 자체는 상당히 간단하다.)

그 다음으로 Recursion을 위해 재귀함수에 어떤 파라미터들을 명시적으로 주어여 할 지가 헷갈렸다.

알고리즘 자체는 어렵지 않고 구현력이 조금 필요했던 문제가 아니었나 싶다. 최대한 주석 없이 코드를 해석할 수 있게끔 메서드들을 응집력 있게 나누었다.

Bong5's Tech Blog