2019 KAKAO BLIND RECRUITMENT 후보키 Swift

Source Code

---

Solution

---

1. 컬럼의 크기에서 1개부터 컬럼의 갯수만큼 순서 상관없이 뽑을 때의 조합을 모두 구해준다.

 

ex) 컬럼이 4개일 때 1개를 뽑는 조합 = [0],[1],[2],[3]

      컬럼이 4개일 때 2개를 뽑는 조합 = [0,1],[0,2],[0,3],[1,2],[1,3],[2,3]

      컬럼이 4개일 때 3개를 뽑는 조합 = [0,1,2],[0,1,3],[0,2,3],[1,2,3]

     컬럼이 4개일 때 3개를 뽑는 조합 =  [0,1,2,3]

 

2.조합에 후보키가 포함되는지 확인 (최소성 검증)

 

후보키가 [0],[1,2]가

현재 조합이 [0,1] 이라면 조합 안에 후보키 중 [0]이 포함되므로 최소성에 부합하지 않는다.

현재 조합이 [3] 이라면 조합 안에 후보키 중 어떤 것도 포함되지 않으므로 최소성에 부합한다.

 

3.. 조합들을 인덱스로 Relation안에 각 행의 속성들을 모아 배열로 만들고 그 배열들 중 중복이 있는지 확인 (유일성 검증)

 

ex) Relation이 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 이고

조합이 [0,1,2]일 경우에 각 relation의 행에서 인덱스가 0,1,2인 것들을 모두 모아준다.

-> ["100","ryan","music"],["200","apeach","math"],["300","tube","computer"],["400","con","computer"],["500","muzi","music"],["600","apeach","music"]

만약 중복이 없다면 Relation의 행의 갯수와 같을 것이다. 그렇다면 후보키에 넣어줌

 

Problem

---

코딩테스트 연습 - 후보키

Reference

---

 

 

Combination 조합

조합을 구할 때 삼쓰님 블로그를 참조했습니다.

 

새롭게 알게 된것

 

A배열안에 B배열이 모두 포함되는지 아는 방법

 

A배열의 Set로 만들어준뒤 isSuperSet(of:) 메소드를 사용하여 B가 포함되는지 확인한다.

 

순서없이 뽑는 조합을 구하는 법

 

1 2 3 4 5 6 7 8 9 10 11 12 13

//n개중 m를 순서에 상관없이 뽑아야할 조합들을 만들어주는 함수 func combination(n: [Int], m: Int, current index: Int, pickedArray: [Int]) {     if m == 0 {         cases.append(pickedArray)     }else if index == n.count {         return     }else {         var newSelected = pickedArray         newSelected.append(n[index])         combination(n: n, m: m-1, current: index+1, pickedArray: newSelected)         combination(n: n, m: m, current: index+1, pickedArray: pickedArray)     } } Colored by Color Scripter

 

 

2단계를 모두 푼줄 알았더니 후보키가 남아있었네....ㅎㅎㅎ 진짜 다 풀었다!!