kakao 2019 blind recruitment
문제 링크 :
https://programmers.co.kr/learn/courses/30/lessons/42890
내가 생각한 문제 풀이
[시도1]
1. relation의 index를 담고있는 리스트를 만들었다 (컴비네이션 쉽게 하기 위함)
2.1부터 전체까지 combination을 만들었다. 만들어서 temp에 해당 키에 대응하는 값들의 리스트를 만들었다
(이 과정이 오래 걸림)
3.중복제거를 하여 원래 relation의 길이와 비교
이 때 이차원 리스트는 set을 바로 할 수 없기 때문에
내부 리스트를 tuple로 만들어 준 뒤 연산할 수 있다
4)선택된 candkey 중 포함관계에 있는 것이 있다면 제거를 해 준다.
이를 통해 미친반복문의 코드가 완성되었다.
시간 / 결과 / 패착
[시도1]
결과 : 정답
패착 :
시간이 오래 걸렸다는 게 문제
해답 코드를 보면 확인할 수 있듯이
1) 전체 조합
2) 유일성
3) 최소성
부분을 따로 두어서 검증했음을 알 수 있다.
나의 경우 맨 처음에는 전체조합 유일성 최소성 검사를 매번 하려고 했으나 너무 복잡해서 최소성은 따로 떼어 풀었다.
문제 해설
컴비 유일 최소 확인
코드
나의 정답 코드
from itertools import combinations
from copy import deepcopy
def solution(relation):
len_relation = len(relation)
rel = [i for i in range(len(relation[0]))]
candkey = []
for i in range(1, len_relation+1):
check = list(combinations(rel, i))
for che in check:
temp = []
for idx, item in enumerate(relation):
now = []
for c in che:
now.append(relation[idx][c])
temp.append(tuple(now))
if len(set(temp)) == len_relation:
candkey.append(che)
print(candkey)
answer = deepcopy(candkey)
# candkey 중복제거
for i in range(len(candkey)):
for j in range(i+1, len(candkey)):
if len(candkey[i]) == len(set(candkey[i])&set(candkey[j])):
if candkey[j] in answer:
answer.remove(candkey[j])
return len(answer)정답 코드
from itertools import combinations as combi
def solution(relation):
row = len(relation)
col = len(relation[0])
# 전체 조합
candidates = []
for i in range(1, col+1):
candidates.extend(combi(range(col), i))
print(candidates)
# 유일성
unique = []
for candi in candidates:
tmp = [tuple([item[i] for i in candi]) for item in relation]
if len(set(tmp)) == row:
unique.append(candi)
# 최소성
answer = set(unique)
for i in range(len(unique)):
for j in range(i+1, len(unique)):
if len(unique[i]) == len(set(unique[i] & set(unique[j]))):
answer.discard(unique[j])
return len(answer)추가 공부
이차원 리스트의 중복확인
set을 이용하기 위해서는 tuple로 만들어야 한다
python
# [[1,2], [1,3], [1,4]]일 때 바깥쪽 리스트에서만 중복 여부를 확인하고 싶다면
new = [tuple(item) for item in items]
# 안의 것도 중복 제거 하고 싶다면
new2 = set([tuple(set(item)) for item in items]문제 해결 시 가장 바깥쪽부터 리스트 만들면서 그 변수의 예시를 주석으로 쓰면서 확인하면 쉽게 할 수 있다
포함관계 중복 제거
candkey 중복 제거 과정에서 튜플 간의 포함 관계를 확인해야 했다
list 쓸때 사용하는 in은 원소 하나만 사용하는 것이라서 불가
이 상황에서
len(비교 기준) == len(set(비교기준)&set(비교대상))
을 했을 때 같으면 포함되어 있는 것이다
tip for me
어느 순간부터 코테 문제들이 잘 안풀리고
자의적인 해석으로 테스트코드만 맞는 문제들이 발생해서
과감하게 level2 정복 프로젝트를 시작했다
간단한 코테 문제들까지 모두 쓰기에는 시간 아깝다는 생각이 들어 노션에 간단한 메모로 대체하던 중
파이썬 테크닉의 결정체 같은 문제를 발견해 블로그에 기록한다.
이 문제는 푸는데 꽤 오래 걸렸다.
어떻게 푸는지 핵심 아이디어는 읽자마자 떠올랐는데
반복문이 좀 많고 복잡해서 어떤 반복문을 먼저 구현할지 등을 고민하는 데 시간이 오래 걸렸고 에러도 몇 번 떴다
문제 자체는 단순한데 이런 문제를 풀 때 말렸다는 생각이들면
그 순간 여태까지 쓴 코드는 메모해두고 새로 시작하자
차근차근 디버깅과 주석을 잘 쓰면서
한 단계씩 처리하는 게 오히려 시간이 덜 걸리는 길이다.
