프로그래머스 후보키

풀이

• 후보키를 만들어서 중복이 없는지 체크하는 문제.
  • 조합만드는 건
    • for문을... for문 말고 좀 편한거 없나? 조합 만들어야 되네. 4+3+2+1...
    • 아! 1은 필요없다. 다 들어있는거라서... 4+3+2
  • 그리고 중복 체크는 카운터 쓰면 될 듯?
    • 속도는 좀 포기하고 편하게 가자...
• 뭘 써야하나? 일단 itertools가 생각났다.
  • https://docs.python.org/ko/3/library/itertools.html

itertools — Functions creating iterators for efficient looping

• 콤비네이션 쓰면 되지?
  • 아니다. 거꾸로 조합할 수도 있잖아?
  • 아닌가? 정방향 조합해서 중복이면 역방향 조합해도 중복이잖아?
  • 그냥 콤비네이션이 맞네?

product('ABCD', repeat=2)	AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
permutations('ABCD', 2)	AB AC AD BA BC BD CA CB CD DA DB DC
combinations('ABCD', 2)	AB AC AD BC BD CD
combinations_with_replacement('ABCD', 2)	AA AB AC AD BB BC BD CC CD DD

• 그러니까 아래와 같은 경우는

• 이렇게 섞어야 하는데...?
  • 응? 9개 넘네.

for i in range(1,4):
    a = combinations(["학번","이름","전공","학년"], i)
    for aa in a:
        print(aa)
            
출력 〉
('학번',)
('이름',)
('전공',)
('학년',)
('학번', '이름')
('학번', '전공')
('학번', '학년')
('이름', '전공')
('이름', '학년')
('전공', '학년')
('학번', '이름', '전공')
('학번', '이름', '학년')
('학번', '전공', '학년')
('이름', '전공', '학년')

• 4개 중에 1개 뽑아 : 4개 = 4C1 = 4P1 / 1P1
• 4개 중에 2개 뽑아(중복없이) : 6개 = 4C2 = 4P2 / 2P2
• 4개 중에 3개 뽑아(중복없이) : 4개 = 4C3 = 4P2 / 3P3

• 하... 나 수포자라 수학 공부하고 있엉.
• ㅋㅋㅋ

from itertools import combinations

def solution(relation):
    answer = 0
    C = len(relation[0])

    for i in range(1, C):
        a = combinations([i for i in range(C)], i)
        for aa in a:
            print(aa)
    
    return answer
    
출력 〉
(0,)
(1,)
(2,)
(3,)
(0, 1)
(0, 2)
(0, 3)
(1, 2)
(1, 3)
(2, 3)
(0, 1, 2)
(0, 1, 3)
(0, 2, 3)
(1, 2, 3)

• 자! 이제 무지성 코딩을 시작하지!
  • 땡!

from itertools import combinations

def solution(relation):
    answer = 0
    C = len(relation[0])

    
    for i in range(1, C):
        a = combinations([i for i in range(C)], i)
        for aa in a:
            _txt_array = []
            for l in range(len(relation)):
                _txt = ""
                for aaa in aa:
                    _txt += relation[l][aaa]
                _txt_array.append(_txt)
            len_source = len(_txt_array)
            len_target = len(list(set(_txt_array)))
            if len_source == len_target:
                answer += 1
    return answer
    

테스트 1
입력값 〉	[["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
실행 결과 〉	실행한 결괏값 9이 기댓값 2과 다릅니다.

• 이상하다 .ㅡ.ㅡ.
  • 아. 1개 짜리로 성공했으면 그건 지워야 하는구나?

• 성공한 조합을 뺄려고 했더니...
  • 콤비네이션에는 remove( ) 함수가 없다.
• 머리가 돌이라서 하루 지났다. ㅋㅋㅋ
  • 테스트케이스를 하나 추가해보았다.
  • 필드 자체가 중복일 경우...

• 이렇게 필드 자체가 중복이면... 후보키를 아예 못 만들지?
  • 근데 그러면 해당 필드를 통으로 지워버려도 되는데...
    • 이걸 확인해서 지우면 속도가 좀 빨라지려나?
      • 하지만 이미 지금 빠른걸...ㅡ.ㅡ;
      • 어차피 길이도, 8, 20, 8이라서 다 곱해봤자 1280밖에 안됨.
• 아. 이건가?!
  • "후보 키의 최대 개수를 구하라."
    • 중복을 지우고 있었는데, 그게 아니라 중복을 최대한 많이 많들어서... 최소성을 나중에 체크하는건가!?
    • 왠지 그런 듯... 그러면 answer+=1이 아니라 중복까지 전부 리스트에 때려넣고.
      • 그 리스트를... 어떻게 하지? 일단 리스트 부터 만들자!
      • 어쩐지... 1280개 밖에 안되더라니... 그럴리가 없지. 쳇.
• 코드 수정... 먼저 조합을 다 만들어서 배열에 넣고

• 배열 안에 중복이 있으면 제거하고.
  • if len(_tmp) == len(list(set(_tmp))): 으로
  • 이러면 내가 만든 중복 100%의 테스트 케이스는 여기서 걸러지고,

• 만들어진 조합(Candidate Key) 배열에서 최대한 많은 키를 뽑아낼 수 있는... 어떻게 찾아ㅋ
  • ...는 Candidate Key에서 중복했던 애들 지울 때, Comb 배열에서도 조합을 지워버리면 되겠다.
  • 그러면 이렇게 남고... 여기서 중복된 원소 빼고 제일 많이 살아남는걸 찾으면 되는데...

• 여기서 멈춤 ㅋㅋㅋ
  • (0,), (0, 1), (0, 2), (0, 3), (1, 2), (0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)
    • 여기서... (0)을 선택하면, 6개 못 쓰고,
    • (0,1)을 선택하면, 0과 1을 못 쓴다.
      • 근데... 이게 맞나?
      • 길이가 짧은 애들부터... 처리?
        • 조합자체가 길이가 짧은 애들부터 되어 있긴 함.
          • 지져분 하지만, 점심 빨리 먹고 30분 동안 생각한 걸로 짜봄.

from itertools import combinations

def solution(relation):
    answer = 0
    Field = [i for i in range(len(relation[0]))]
    
    Comb = [] # 필드 인덱스로 조합 만들기
    for i in range(1, len(Field)):
        Comb += list(combinations(Field, i))
    
    CandiKey = [] # 실제 후보키 만들기
    for c in Comb:
        _tmp = []
        for r in range(len(relation)):
            _txt = ""
            for cc in c:
                _txt += relation[r][cc]
            _tmp.append(_txt)
        if len(_tmp) == len(list(set(_tmp))):
            CandiKey.append(_tmp)
        else:
            Comb.remove(c)
            Comb.insert(0,[])
            
    Comb = [c for c in Comb if len(c) > 0] # remove 쓸때 인덱스 안바뀌게 하려고 insert한 빈칸 지우기
    
    print(answer, Comb)
    while len(Comb) > 0:
        x = Comb.pop(0)
        answer += 1
        for xx in x:
            for i in range(len(Comb)):
                if xx in Comb[i]:
                    Comb[i] = []
        Comb = [c for c in Comb if len(c) > 0]
        print(answer, Comb)
        
    return answer

• 테케 잘 돔. 아침에도 테케는 잘 돔. 걱정

테스트 1
입력값 〉	[["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
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	0 [(0,), (0, 1), (0, 2), (0, 3), (1, 2), (0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]
1 [(1, 2), (1, 2, 3)]
2 []

테스트 2
입력값 〉	[["100", "ryan", "music", "2"], ["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
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	0 []

• 실패함.
  • ㅋㅋㅋ 아놔

정확성  테스트
테스트 1 〉	실패 (0.04ms, 10.2MB)
테스트 2 〉	실패 (0.05ms, 10.1MB)
테스트 3 〉	실패 (0.06ms, 10.1MB)
테스트 4 〉	실패 (0.06ms, 10.3MB)
테스트 5 〉	실패 (0.05ms, 10.3MB)
테스트 6 〉	실패 (0.00ms, 10.2MB)
테스트 7 〉	통과 (0.01ms, 10.2MB)
테스트 8 〉	실패 (0.01ms, 10.2MB)
테스트 9 〉	실패 (0.07ms, 10.3MB)
테스트 10 〉	통과 (0.10ms, 10.2MB)
테스트 11 〉	실패 (0.24ms, 10.3MB)
테스트 12 〉	통과 (2.86ms, 10.4MB)

• 이거... 인덱스 조합으로 하는게 아니라 그냥 후보키 끼리 비교해야 하는건가?
  • 아... 혹시 순서가? 그렇구나!
    • (0)은 하나니까 그냥 쭈욱 비교하면서 지우면 되는거구...
    • (1,2)(1,2,3)은, (1,2,3)에 (1,2)가 포함되어 있어서... ㅠ.ㅠ;
      • 실패

    Comb = [c for c in Comb if len(c) > 0] # remove 쓸때 인덱스 안바뀌게 하려고 insert한 빈칸 지우기
    Final_Comb = []
    while len(Comb) > 0:
        answer += 1
        x = Comb.pop(0)
        Final_Comb.append(x)
        xlen = len(x)
        for ci in range(len(Comb)):
            clen = len(Comb[ci])
            for i in range(clen-xlen+1):
                is_subset = True
                #rint(x, Comb[ci])
                for xi in range(xlen):
                    if x[xi] != Comb[ci][i+xi]:
                        #rint(x[xi], Comb[ci][i+xi], end=" ")
                        is_subset = False
                        break
                if is_subset == True:
                    #rint("삭제")
                    Comb[ci] = []
                    break
                #rint("메롱")
        Comb = [c for c in Comb if len(c) > 0]
        print(answer, x, Comb)
    print(Final_Comb)

• print문 덕지 덕지 붙여서 계속 보다보니, 
  • 아... (0,2)랑 (0,2,4)가 있으면 (0,2,4)도 안되고, (0,1,2)도 안되는거구나?
    • 이러면 순서대로 비교할 필요없이...? 그냥 빼면 되는거 아닌가?
  • 결국 문제를 제대로 이해를 못 했다는 걸로 결론.
    • 이것도 실패.... 너무하네. 문제나 다시 읽어보자.

from itertools import combinations

def solution(relation):
    answer = 0
    Field = [i for i in range(len(relation[0]))]
    
    Comb = [] # 필드 인덱스로 조합 만들기
    for i in range(1, len(Field)):
        Comb += list(combinations(Field, i))
    
    CandiKey = [] # 실제 후보키 만들기
    for c in Comb:
        _tmp = []
        for r in range(len(relation)):
            _txt = ""
            for cc in c:
                _txt += relation[r][cc]
            _tmp.append(_txt)
        if len(_tmp) == len(list(set(_tmp))):
            CandiKey.append(_tmp)
        else:
            Comb.remove(c)
            Comb.insert(0,[])
            
    Comb = [c for c in Comb if len(c) > 0] # remove 쓸때 인덱스 안바뀌게 하려고 insert한 빈칸 지우기
    final_Comb = []
    while len(Comb) > 0:
        answer += 1
        x = Comb.pop(0)
        final_Comb.append(x)
        for i in range(len(Comb)):
            if set(Comb[i]) == set(Comb[i])|set(x):
                Comb[i] = []
        Comb = [c for c in Comb if len(c) > 0]
    
    return len(final_Comb)
    
정확성  테스트
테스트 1 〉	통과 (0.06ms, 10.3MB)
테스트 2 〉	통과 (0.08ms, 10.3MB)
테스트 3 〉	통과 (0.05ms, 10.4MB)
테스트 4 〉	통과 (0.05ms, 10.2MB)
테스트 5 〉	실패 (0.08ms, 10.2MB)
테스트 6 〉	실패 (0.01ms, 10.3MB)
테스트 7 〉	통과 (0.02ms, 10.3MB)
테스트 8 〉	실패 (0.02ms, 10.3MB)
테스트 9 〉	통과 (0.11ms, 10.3MB)
테스트 10 〉	통과 (0.14ms, 10.3MB)
테스트 11 〉	통과 (0.32ms, 10.3MB)
테스트 12 〉	통과 (2.57ms, 10.3MB)
테스트 13 〉	통과 (0.36ms, 10.4MB)
테스트 14 〉	통과 (0.06ms, 10.3MB)
테스트 15 〉	통과 (0.06ms, 10.4MB)
테스트 16 〉	통과 (0.05ms, 10.4MB)
테스트 17 〉	통과 (0.09ms, 10.4MB)
테스트 18 〉	통과 (3.82ms, 10.4MB)
테스트 19 〉	통과 (3.22ms, 10.2MB)
테스트 20 〉	통과 (3.82ms, 10.4MB)
테스트 21 〉	실패 (2.77ms, 10.4MB)
테스트 22 〉	통과 (1.70ms, 10.2MB)
테스트 23 〉	통과 (0.13ms, 10.4MB)
테스트 24 〉	통과 (2.30ms, 10.3MB)
테스트 25 〉	통과 (3.24ms, 10.4MB)
테스트 26 〉	통과 (2.61ms, 10.3MB)
테스트 27 〉	통과 (0.32ms, 10.3MB)
테스트 28 〉	통과 (0.43ms, 10.4MB)

• 아............ 난 병신이다. 병신이야....
  • 맨 처음에 조합 만들때... len(Field)+1을 안해줘서 하나 모자랐던 거야.
    • 실패
      •     Comb = [] # 필드 인덱스로 조합 만들기
            for i in range(1, len(Field)):
                Comb += list(combinations(Field, i))
    • 성공
      •     Comb = [] # 필드 인덱스로 조합 만들기
            for i in range(1, len(Field)+1):
                Comb += list(combinations(Field, i))
  • 하하하하하하하하하하하하하하하

from itertools import combinations

def solution(relation):
    answer = 0
    Field = [i for i in range(len(relation[0]))]
    
    Comb = [] # 필드 인덱스로 조합 만들기
    for i in range(1, len(Field)+1):
        Comb += list(combinations(Field, i))
    
    CandiKey = [] # 실제 후보키 만들기
    for c in Comb:
        _tmp = []
        for r in range(len(relation)):
            _txt = ""
            for cc in c:
                _txt += relation[r][cc]
            _tmp.append(_txt)
        if len(_tmp) == len(list(set(_tmp))):
            CandiKey.append(_tmp)
        else:
            Comb.remove(c)
            Comb.insert(0,[])
    Comb = [c for c in Comb if len(c) > 0]
    #print(CandiKey)
    #print(Comb)
    
    final_Comb = []
    while len(Comb) > 0:
        answer += 1
        x = Comb.pop(0)
        final_Comb.append(x)
        for i in range(len(Comb)):
            #print(x, Comb[i])
            if set(Comb[i]) == set(Comb[i])|set(x):
                Comb[i] = []
        Comb = [c for c in Comb if len(c) > 0]
    #print(final_Comb)
    return len(final_Comb)
    
정확성  테스트
테스트 1 〉	통과 (0.10ms, 10.3MB)
테스트 2 〉	통과 (0.09ms, 10.4MB)
테스트 3 〉	통과 (0.09ms, 10.4MB)
테스트 4 〉	통과 (0.06ms, 10.1MB)
테스트 5 〉	통과 (0.05ms, 10.3MB)
테스트 6 〉	통과 (0.02ms, 10.3MB)
테스트 7 〉	통과 (0.02ms, 10.3MB)
테스트 8 〉	통과 (0.02ms, 10.4MB)
테스트 9 〉	통과 (0.12ms, 10.3MB)
테스트 10 〉	통과 (0.25ms, 10.2MB)
테스트 11 〉	통과 (0.19ms, 10.4MB)
테스트 12 〉	통과 (1.60ms, 10.3MB)
테스트 13 〉	통과 (0.37ms, 10.3MB)
테스트 14 〉	통과 (0.06ms, 10.3MB)
테스트 15 〉	통과 (0.09ms, 10.1MB)
테스트 16 〉	통과 (0.06ms, 10.2MB)
테스트 17 〉	통과 (0.09ms, 10.3MB)
테스트 18 〉	통과 (5.33ms, 10.4MB)
테스트 19 〉	통과 (1.88ms, 10.3MB)
테스트 20 〉	통과 (3.70ms, 10.3MB)
테스트 21 〉	통과 (2.55ms, 10.2MB)
테스트 22 〉	통과 (1.65ms, 10.3MB)
테스트 23 〉	통과 (0.08ms, 10.3MB)
테스트 24 〉	통과 (2.39ms, 10.3MB)
테스트 25 〉	통과 (3.07ms, 10.4MB)
테스트 26 〉	통과 (4.35ms, 10.2MB)
테스트 27 〉	통과 (0.33ms, 10.4MB)
테스트 28 〉	통과 (0.49ms, 10.2MB)

이것 때문에 이틀을 고생했네...

• 고수의 풀이.
  • 내것보다 빠르고 코드가 더 예쁜 것들 위주로

def solution(relation):
    def is_powerset(parent, child):
        return parent | child == parent

    n_attr = len(relation[0])
    candidate_key = []

    for key in range(1, 1 << n_attr):
        # 현재까지 찾은 후보키을 부분집합으로 가지지 않는지를 먼저 판단
        flag = False
        for e in candidate_key:
            if is_powerset(key, e):
                flag = True
                break
        if flag:
            continue

        # 현재 키가 유일성을 만족하는지를 판단
        sliced_relation = []
        for row in relation:
            sliced_row = []
            for j in range(0, n_attr):
                # print(bin(copied_key >> j))
                if (key >> j) & 1 == 1:
                    sliced_row.append(row[j])
            sliced_relation.append(tuple(sliced_row))

        if len(sliced_relation) != len(set(sliced_relation)):
            continue

        # 후보키 목록에 추가
        candidate_key.append(key)

    answer = len(candidate_key)
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.4MB)
테스트 2 〉	통과 (0.04ms, 10.2MB)
테스트 3 〉	통과 (0.06ms, 10.4MB)
테스트 4 〉	통과 (0.06ms, 10.3MB)
테스트 5 〉	통과 (0.10ms, 10.2MB)
테스트 6 〉	통과 (0.01ms, 10.3MB)
테스트 7 〉	통과 (0.01ms, 10.3MB)
테스트 8 〉	통과 (0.02ms, 10.4MB)
테스트 9 〉	통과 (0.14ms, 10.3MB)
테스트 10 〉	통과 (0.04ms, 10.1MB)
테스트 11 〉	통과 (0.16ms, 10.3MB)
테스트 12 〉	통과 (2.10ms, 10.4MB)
테스트 13 〉	통과 (0.21ms, 10.3MB)
테스트 14 〉	통과 (0.04ms, 10.3MB)
테스트 15 〉	통과 (0.04ms, 10.2MB)
테스트 16 〉	통과 (0.05ms, 10.2MB)
테스트 17 〉	통과 (0.07ms, 10.3MB)
테스트 18 〉	통과 (0.88ms, 10.2MB)
테스트 19 〉	통과 (1.62ms, 10.2MB)
테스트 20 〉	통과 (1.68ms, 10.3MB)
테스트 21 〉	통과 (5.26ms, 10.2MB)
테스트 22 〉	통과 (1.99ms, 10.3MB)
테스트 23 〉	통과 (0.05ms, 10.3MB)
테스트 24 〉	통과 (0.78ms, 10.3MB)
테스트 25 〉	통과 (1.00ms, 10.1MB)
테스트 26 〉	통과 (2.36ms, 10.2MB)
테스트 27 〉	통과 (0.31ms, 10.3MB)
테스트 28 〉	통과 (0.78ms, 10.2MB)

• 이쪽도 고수

from itertools import combinations

def solution(relation):
    row = len(relation)
    col = len(relation[0])

    combi_list = []
    for i in range(1, col +1):
        combi_list.extend(combinations(range(col),i))

    answer_list = []
    for i in combi_list:
        tmp = [tuple([item[key] for key in i]) for item in relation]

        if len(set(tmp)) == row: # 유일성 확인
            flag = True

            for j in answer_list:
                if set(j).issubset(set(i)): # 최소성 확인 j가 i의 sub 인지 확인
                    flag = False
                    break

            if flag : answer_list.append(i)


    answer = len(answer_list)
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.2MB)
테스트 2 〉	통과 (0.06ms, 10.1MB)
테스트 3 〉	통과 (0.04ms, 10.2MB)
테스트 4 〉	통과 (0.04ms, 10.1MB)
테스트 5 〉	통과 (0.08ms, 10.3MB)
테스트 6 〉	통과 (0.01ms, 10.3MB)
테스트 7 〉	통과 (0.02ms, 10.3MB)
테스트 8 〉	통과 (0.01ms, 10.3MB)
테스트 9 〉	통과 (0.08ms, 10.2MB)
테스트 10 〉	통과 (0.11ms, 10.2MB)
테스트 11 〉	통과 (0.31ms, 10.2MB)
테스트 12 〉	통과 (1.03ms, 10.2MB)
테스트 13 〉	통과 (0.49ms, 10.2MB)
테스트 14 〉	통과 (0.04ms, 10.2MB)
테스트 15 〉	통과 (0.05ms, 10.2MB)
테스트 16 〉	통과 (0.05ms, 10.3MB)
테스트 17 〉	통과 (0.08ms, 10.4MB)
테스트 18 〉	통과 (4.58ms, 10.2MB)
테스트 19 〉	통과 (1.36ms, 10.2MB)
테스트 20 〉	통과 (5.16ms, 10.2MB)
테스트 21 〉	통과 (3.78ms, 10.2MB)
테스트 22 〉	통과 (1.11ms, 10.2MB)
테스트 23 〉	통과 (0.06ms, 10.3MB)
테스트 24 〉	통과 (1.27ms, 10.3MB)
테스트 25 〉	통과 (3.01ms, 10.2MB)
테스트 26 〉	통과 (2.18ms, 10.2MB)
테스트 27 〉	통과 (0.45ms, 10.1MB)
테스트 28 〉	통과 (0.72ms, 10.4MB)

고수들의 코드를 보면... 내가 참 바보 같다. 싶다...