세용용용용
2024. 7. 8. 10:17
업데이트 사항
수정 : 2024-07-08 [시간 복잡도 추가]
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
나의 코드
# 2024-07-08
from itertools import combinations
def candi_check(now_list, candidate_key):
for i in candidate_key:
if i.issubset(now_list):
return False
return True
def solution(relation):
answer = 0
id_list = [i for i in range(len(relation[0]))]
candidate_key = []
for len_combi in range(1, len(id_list)+1):
for combi in combinations(id_list, len_combi):
combi=set(combi)
if candi_check(combi, candidate_key):
set_list = set()
for now_row in relation:
now_list = []
for now_index in combi:
now_list.append(now_row[now_index])
set_list.add(' '.join(now_list))
# 유일성
if len(set_list)==len(relation):
answer+=1
candidate_key.append(combi)
return answer
시간 복잡도
id_list : 인덱스 리스트 만들기( 선형시간 )
for len_combi in range(1, len(id_list)+1) : combinations 길이 변수 ( 선형시간 )
combinations : ( 지수시간 )
candi_check : 부분 집합 체크 ( 선형 시간 )
for now_row in relation : 릴레이션 리스트 순회 ( 선형 시간 )
for now_index in combi : combinations 산출물 순회 ( 선형 시간 )
3차형 * 지수형 시간 복잡도를 가짐
즉, 최악의 경우 O(2**n)