programmers.co.kr/learn/courses/30/lessons/42890
코딩테스트 연습 - 후보키
[["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
programmers.co.kr
안녕하세요 후르륵짭짭 입니다
저는 이 문제를 정말 복잡하게 풀었습니다.
그래서 한시간 정도 걸린 문제였습니다!
** 저의 풀이 **
// 1: 16
var combi : [[Int]] = []
var isMinum : Bool = true
func solution(_ relation:[[String]]) -> Int {
var list : [Int] = []
for start in 0..<relation[0].count{
list.append(start)
}
for find in 1...relation[0].count{
combination(0, 0, find, list, [])
}
var uniquList : [[Int]] = []
for element in combi{
//유일성을 만족하는가
if isprimary(element, relation){
uniquList.append(element)
}
}
// for element in uniquList {
// print(element)
// }
// print("정답")
var answer = 0
//최소성을 만족하는가
for unique in uniquList {
let index = uniquList.firstIndex(of: unique)!
uniquList.remove(at: index)
for start in 1...unique.count{
// print("start : \(start)")
if isMinum {
minumlity(0, start, 0, unique, [], uniquList)
}
else{
break
}
if start == unique.count && isMinum{
print(unique)
answer += 1
}
}
uniquList.insert(unique, at: index)
isMinum = true
}
return answer
}
func minumlity(_ current : Int , _ max : Int, _ index : Int ,_ list : [Int], _ answer : [Int] ,_ unique : [[Int]]){
var temp = list
var tempAnswer = answer
// print("temp : \(temp) ")
if isMinum == true {
if current == max {
if unique.contains(answer) {
// print(answer)
isMinum = false
}
}
else{
for start in index..<list.count{
let item = temp[start]
temp.remove(at: start)
tempAnswer.append(item)
minumlity(current + 1, max, start, temp, tempAnswer, unique)
temp.insert(item, at: start)
tempAnswer.removeLast()
}
}
}
}
func isprimary(_ element : [Int], _ relation : [[String]]) -> Bool {
var diction : [String : Int] = [:]
//make String
for tuple in relation{
var inputString : String = ""
for (index, single) in tuple.enumerated(){
for elementSingle in element {
if elementSingle == index {
inputString += single + " "
}
}
}
if let _ = diction[inputString] {
return false
}
else{
diction[inputString] = 1
}
}
return true
}
func combination(_ current : Int , _ index : Int , _ max : Int, _ list : [Int], _ answer: [Int]){
var temp = list
var tempAnswer = answer
if current == max {
combi.append(answer)
}
else{
for start in index..<temp.count {
let item = temp[start]
temp.remove(at: start)
tempAnswer.append(item)
combination(current + 1, start, max, temp, tempAnswer)
temp.insert(item, at: start)
tempAnswer.removeLast()
}
}
}
코드가 정말 깁니다....
일단 이 문제를 풀기 위해서는 데이터베이스의 유일성과 최소성에 대해서 알아야합니다.
유일성은 구분 될 수 있는 요소가 되어야하는 것을 의미합니다.
예를 들어 테이블의 속성이 "학번", "과목", "성별 - 중복 존재" 이라 한다면 성별을 제외하고 "학번" / "과목" 으로 구분 할 수 있지만 성별로는 불가능합니다. 이런 것 처럼 구분할 수 있는 것을 유일성이라 합니다. 유일성은 "학번 + 성별" 도 가능하고 "과목 + 성별" 이렇게 해도 유일성이 됩니다.
최소성은 구분 해줄 수 있는 키가 최소 한개 여야 하는 것을 의미합니다.
예를 들어 "학번 + 성별" 이라고 하면 이 후보키는 "학번" 덕분에 구분 할 수 있게 됐습니다. 하지만! "학번 + 과목 + 성별" 이렇게 되도 유일성을 만족하지만 쓸대없이 "학번" 과 " 과목" 이 두개 들어 있습니다. 둘중에 하나만 있어도 되는데,,,
이게 바로 최소성 입니다. ㅎㅎㅎ
이제 본격적으로 코드를 설명하도록 하겠습니다.
func combination(_ current : Int , _ index : Int , _ max : Int, _ list : [Int], _ answer: [Int]){
var temp = list
var tempAnswer = answer
if current == max {
combi.append(answer)
}
else{
for start in index..<temp.count {
let item = temp[start]
temp.remove(at: start)
tempAnswer.append(item)
combination(current + 1, start, max, temp, tempAnswer)
temp.insert(item, at: start)
tempAnswer.removeLast()
}
}
}저는 이 코드로 일단 조합을 만들어 줬습니다. 왜냐하면 키의 조합을 만들어줘야하기 때문입니다.
속성이 1, 2, 3 이라고 한다면 [1][2][3][1 2][1 3][2 3][1 2 3] 이렇게 만들어줘야합니다. 그래서 이렇게 해준 겁니다.
이제 유일성 여부를 판단해줍니다.
func isprimary(_ element : [Int], _ relation : [[String]]) -> Bool {
var diction : [String : Int] = [:]
//make String
for tuple in relation{
var inputString : String = ""
for (index, single) in tuple.enumerated(){
for elementSingle in element {
if elementSingle == index {
inputString += single + " "
}
}
}
if let _ = diction[inputString] {
return false
}
else{
diction[inputString] = 1
}
}
return true
}저는 그래서 Dictionary를 이용해서 중복성 여부를 판단해줬습니다.
만약에 유일성의 조합이 1 3 이라고 한다면 relation 을 완전 탐색하면서 속성의 위치가 1 3 일때 String으로 저장해서
후에 Dictionary로 중복여부를 판단해줬습니다 ㅎㅎㅎ
최소성 여부 판단
func minumlity(_ current : Int , _ max : Int, _ index : Int ,_ list : [Int], _ answer : [Int] ,_ unique : [[Int]]){
var temp = list
var tempAnswer = answer
// print("temp : \(temp) ")
if isMinum == true {
if current == max {
if unique.contains(answer) {
// print(answer)
isMinum = false
}
}
else{
for start in index..<list.count{
let item = temp[start]
temp.remove(at: start)
tempAnswer.append(item)
minumlity(current + 1, max, start, temp, tempAnswer, unique)
temp.insert(item, at: start)
tempAnswer.removeLast()
}
}
}
}최소성에 대한 검사는 유일성을 거진 조합이[ 1 3 ]이라고 할 때,
유일성을 가지는 모든 경우에서[ 1 3 ]의 경우를 제외하고 [1] 일 있거나 [3] 이 있다면 최소성을 만족하지 못하기 때문에 제외 시켜 줍니다.
이렇게 하면 통과가 됩니다... 정말 빡구현을 한 거 같습니다
개인적으로 너무 길어서 코드가 별로라는 느낌을 줍니다.... 중복성 검사를 여러번이나 하고,,,
효율성 테스트라고 하면 아마 통과 못 했을 겁니다.
그중에서도 가장 마음에 안든 부분은 최소성 부분입니다.
for x in uniqueArray {
let setTemp = Set(x)
var isOkay = true
for y in result {
if y.isSubset(of: setTemp) {
isOkay = false
break
}
}
if isOkay {
result.append(setTemp)
}
}그래서 새롭게 알게 된 부분이 isSubset 입니다.
이것은 A.isSubset(B)로 사용이 되는데, 의미는 A가 B의 부분 집합인가? 입니다.
따라서 요소 하나하나 확인 하면서 부분 집합인지 확인 해줍니다.
let test1 : Set = ["Alicia", "Bethany", "Chris", "Diana", "Eric"]
let test2 : Set = [ "Alicia", "Bethany" , "Bethany"]
//A에서 B와의 공통점을 빼고 남은 것
let answer = test2.subtracting(test1)
//A가 B의 부분 집한 인가... 모든 원소가 모두 포함 되는가
let issubset = test1.isSubset(of: test2)
if issubset {
print(answer)
//["Eric", "Chris", "Diana"]
}
else{
print("NO")
}
참고 사이트 :
m.blog.naver.com/dlwjddns5/220620195019
[정보처리기사] 기본키, 후보키, 슈퍼키의 차이점을 손쉽게 알아보자!
자, 안녕하세요! 징징이입니다 정보처리기사 공부중인데, 블로그 포스팅도 할겸 관계형 ...
blog.naver.com
developer.apple.com/documentation/swift/set/1783322-subtracting
Apple Developer Documentation
developer.apple.com
developer.apple.com/documentation/swift/set/1787295-issubset
Apple Developer Documentation
developer.apple.com
'Xcode > Swift - Algorithm' 카테고리의 다른 글
| Swift ) 프로그래머스(Lv2) - [1차]프렌즈4블록 (Simulation) (0) | 2020.09.08 |
|---|---|
| Swift ) 프로그래머스(Lv2) - [3차] 방금 그곡 (String) (1) | 2020.09.08 |
| Swift ) 프로그래머스(Lv2) - 오픈 채팅방 (Hash) (0) | 2020.09.08 |
| Swift ) 프로그래머스(Lv2) - [1차] 캐시 (Hash) (0) | 2020.09.07 |
| Swift) 프로그래머스(Lv2) - [1차] 뉴스 클러스터링 (Hash) (0) | 2020.09.06 |
댓글