프로그래머스 코딩테스트 고득점 Kit의 문제입니다.
https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit
코딩테스트 연습
기초부터 차근차근, 직접 코드를 작성해 보세요.
programmers.co.kr
문제
https://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
내가 작성한 코드
from itertools import combinations
from collections import defaultdict
import sys
def used_key(used, selected):
for key in used:
matched = 0
for i in key:
if i not in selected:
break
matched += 1
if matched == len(key):
return True
return False
def solution(relation):
answer = 0
num_row = len(relation)
num_col = len(relation[0])
cols = [i for i in range(num_col)]
used = []
for r in range(1, num_col+1):
for selected in combinations(cols, r):
if used_key(used,selected):
continue
must_have_num_row = set()
for row in relation:
must_have_num_row.add(tuple([row[i] for i in selected]))
if len(must_have_num_row) == num_row:
used.append(selected)
answer += 1
return answer
- key의 길이가 짧은 순으로 "유일성" 확인
- column의 조합
- combination을 이용하여 len(column)까지 모두 뽑아 확인 - 뽑은 column에 대해 모든 row의 값을 set에 append(must_have_num_row)
- len(must_have_num_row) == num_row이면 유일성 만족
- column의 조합
- 탐색하는 후보키가 이미 뽑은 후보키를 포함하면 탐색하지 않음 (최소성)
- used_key
- 찾은 키(used)가 현재 탐색할 키(selected)에 포함되면 True
- used_key
다른 사람이 작성한 코드
from itertools import combinations
def find(candidate):
keys = []
for k in range(2, len(candidate)+1):
for li in combinations(candidate, k):
res = list(zip(*(i for i in li)))
if len(set(res)) != len(res):
continue
for key in keys:
if set(key).issubset(li):
break
else:
keys.append(set(li))
return len(keys)
def solution(relation):
answer = 0
reverse = list(zip(*relation))
candidate = []
for col in reverse:
if len(set(col)) == len(col):
answer += 1
else:
candidate.append(col)
answer += find(candidate)
return answer
https://velog.io/@djagmlrhks3/Algorithm-Programmers-%ED%9B%84%EB%B3%B4%ED%82%A4-by-Python
[Algorithm] Programmers : 후보키 by Python
문제 바로가기 https://programmers.co.kr/learn/courses/30/lessons/42890프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.그의 학
velog.io
- tuple이나 set간의 포함관계 메서드가 있을거라 생각해서 찾아봤더니 역시 있었다
- in으로 확인될까 했는데, tuple이나 set는 원소 취급이 될 수 있으므로 안된다
기억해야할 것
- set 관련 메서드
- issubset
- subset이면 True - isdisjoint
- 교집합이 없으면 True
- issubset
'코딩테스트' 카테고리의 다른 글
[백준][그리디] 휴먼 파이프라인 (0) | 2021.08.30 |
---|---|
[프로그래머스][KAKAO_BLIND][2020] 기둥과 보 설치 (0) | 2021.08.30 |
[프로그래머스][KAKAO_BLIND][2019] 실패율 (0) | 2021.08.30 |
[프로그래머스][KAKAO_BLIND][2020] 자물쇠와 열쇠 (0) | 2021.08.29 |
[프로그래머스][KAKAO_BLIND][2019] 오픈채팅방 (0) | 2021.08.29 |