2019 KAKAO BLIND RECRUITMENT 후보키 Swift

Source Code

---

	import Foundation
	//조합들을 담을 배열
	var cases = [[Int]]()
	func solution(_ relation:[[String]]) -> Int {
	//0부터 컬럼 갯수만큼 숫자를 담고있는 배열
	let colSize = Array(0..<relation[0].count)
	//후보키에 들어갈 배열
	var candidateKeys = [[Int]]()
	//0부터 컬럼길이만큼 각 조합을 구해준다.
	for i in 0..<colSize.count {
	combination(n: colSize, m: i+1, current: 0, pickedArray: [])
	}
	outer: for c in cases {
	//최소성을 만족하는지 확인
	let set = Set(c)
	//후보키들을 탐색
	for key in candidateKeys {
	//후보키 안에 현재 key가 포함된게 있다면 넘어간다.
	if set.isSuperset(of: key) {
	continue outer
	}
	}
	//속성의 집합들을 담을 배열
	var attributeArrays = [[String]]()
	//릴레이션의 행을 탐색해준다.
	for row in relation {
	//속성의 집합을 만들 배열
	var attributeArray = [String]()
	//행의 속성을 attributeArray에 넣어줌
	for i in c {
	attributeArray.append(row[i])
	}
	//유일성을 만족하는지 확인 attributeArray가 attributeArrays에 있는지 확인
	if !attributeArrays.contains(attributeArray) {
	//없다면 넣어줌
	attributeArrays.append(attributeArray)
	}else{
	break
	}
	}
	//유일성을 만족한다면 relation의 갯수와 조합의 갯수들이 같을것이다.
	if attributeArrays.count == relation.count {
	//후보키에 넣어줌
	candidateKeys.append(c)
	}
	}
	return candidateKeys.count
	}
	//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)
	}
	}
	solution([["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]])

view raw 후보키.swift hosted with ❤ by GitHub

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단계를 모두 푼줄 알았더니 후보키가 남아있었네....ㅎㅎㅎ 진짜 다 풀었다!!