https://school.programmers.co.kr/learn/courses/30/lessons/42890
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
from itertools import combinations
def solution(relations):
answer = 0
n,m =len(relations), len(relations[0])
candidates = []
for i in range(1,m+1):
candidates.extend(combinations([x for x in range(m)],i))
unique = []
for candidate in candidates:
tmp = [tuple([relation[i] for i in candidate]) for relation in relations]
if len(set(tmp)) == n:
check = True
for u in unique:
if set(u).issubset(set(candidate)):
check = False
break
if check:
unique.append(candidate)
return len(unique)
해결법 : combination으로 조합을 뽑자!
내가 못푼 이유: 조합까지는 생각했지만 이후의 구현을 어떻게 해야할지 막힘...
해설을 보니, tuple로 값을 조합하고
이후에 row길이와 같은 값만 뽑아서 issubset 으로 비교한다.
issubset() : 부분 집합인지 아닌지 True, False 반환
> 정석 풀이 접근법
- combinations를 이용해 가능한 후보키 조합을 모두 구한다.
- 해당 배열을 돌면서 유일성, 최소성을 확인한다.
- 유일성 : 후보키 조합에 따라 relation을 돌면서 값들을 tuple 형태로 저장한 뒤, set(tuple)의 길이가 relation의 row 수랑 같으면 각자 유일한 값을 가지고 있다는 뜻
- 최소성 : 유일성을 만족하는 조합 중 이미 unique 배열에 들어간 값들이 해당 조합의 부분집합인지 확인, 만약 부분집합이라면 최소성을 만족하지 못한다는 뜻
'💡 Codeing Test > 프로그래머스' 카테고리의 다른 글
| 프로그래머스) 이모티콘 할인행사(python) (0) | 2024.12.31 |
|---|---|
| 프로그래머스) 두 개 뽑아서 더하기 (0) | 2023.03.23 |
| 프로그래머스) 문자열 내 마음대로 정렬하기 (python) (0) | 2023.03.23 |
| 프로그래머스) 최댓값 만들기(2) (JAVA) (0) | 2023.03.05 |
| 프로그래머스) 124나라의 숫자 (Java & Python) (0) | 2023.03.05 |