2019 KAKAO BLIND RECRUITMENT 후보키 파이썬

2019 KAKAO BLIND RECRUITMENT 후보키 파이썬 풀이

바로 이전에 풀었던 캐시와 동일한 2레벨 문제입니다.

오답코드

• 이틀에 걸쳐 3시간 정도 풀어봤습니다. 우선 combinations 모듈을 활용해서 칼럼의 조합을 1부터 가장 큰 값까지 구했고,
• 각각의 원소를 비교하면서 만약 겹치는 것이 없다면 answer에 1을 더해주는 식으로 로직을 구성했습니다.
• 하지만 부족했던 것은, 최소성을 만족시키지 못하는 코드였다는 점과 for문의 사용이 너무 많아서 정확성 뿐 아니라 효율성 측면에서도
  좋지 못한 코드였습니다.

from itertools import combinations
def solution(relation):
    answer = 0
    # print(len(relation))
    # column 갯수
    col_num = len(relation[0])
    mem_num = len(relation)
    num = [i for i in range(col_num)]
    for i in range(1, col_num):
        combi = list(combinations(num, i))
        for j in combi:

            for k in j:
                prel = [[] for _ in range(len(relation))]
                for s in range(mem_num):
                    prel[s].append((relation[s][k]))
                print(prel)
            for t in range(0, len(prel)-1):
                for x in range(1, len(prel)):
                    if prel[t] == prel[x]:
                        break
                answer += 1
            prel = [[] for _ in range(len(relation))]


    return answer


print(solution([["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]]))

정답코드

• 정답코드는 프로그래머스에서 두번째로 가장 많은 좋아요를 받은 코드로 분석했습니다.

접근 방식

1. for문을 이용해서 1부터 입력으로 주어지는 칼럼의 총 갯수까지의 조합을 구합니다.
2. 해당 값은 candidates 리스트에 저장해줍니다.
3. 도출한 조합에 맞춰 입력값으로 주어진 값들의 tuple을 구합니다.
4. set 함수를 이용해서 중복되는 것이 없을 경우, final 리스트에 저장합니다.
5. 방금전까지 유일성을 보장해줬다면, 이후부터 최소성을 보장해줘야 합니다.
6. 현재까지 final 리스트에는 서로 겹치지 않은 정보들이 저장될 수 있도록 하는 칼럼의 조합이 저장되었지만,
7. 문제는 최소성을 보장하지 못하고, 가능한 모든 경우의 수를 저장한 것입니다.
8. 이를 해결하기 위해 if 문을 활용합니다. intersection 함수를 이용하면, 특정 값이 겹치는 지를 확인할 수 있고,
9. 만약 확인한 결과값이 비교 대상의 길이와 동일하다면, 이는 서로 포함관계를 나타낸다고 할 수 있습니다.
10. 따라서 포함관계에서 부모에 해당하는 값을 discard 해주면 answer에는 최소성을 보장한 조합만이 남게 됩니다.

from itertools import combinations
def solution(relation):
    n_row=len(relation)
    n_col=len(relation[0])  #->runtime error 우려되는 부분

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

    final=[]
    for keys in candidates:
        tmp=[tuple([item[key] for key in keys]) for item in relation]
        if len(set(tmp))==n_row:
            final.append(keys)

    answer=set(final[:])
    for i in range(len(final)):
        for j in range(i+1,len(final)):
            if len(final[i])==len(set(final[i]).intersection(set(final[j]))):
                answer.discard(final[j])

    return len(answer)

이번 문제를 풀면서 combinations 모듈을 좀 더 적극적으로 활용해 볼 수 있었습니다.

하지만 append 대신 extend 함수를 활용해서 리스트 자체가 아닌 확장을 해야 하는 상황을 알 수 있었고,

특히 list comprehension과 key값을 활용해서 여러 경우의 조합을 비교할 수 있다는 점도 배웠습니다.

중복 여부를 확인하기 위해서 set함수와 intersection 함수를 적절히 활용하고, set에 대해서는 discard 함수를 통해

원소를 삭제할 수 있다는 점도 배웠습니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady