자료구조 및 알고리즘/알고리즘

[알고리즘] 2020 KAKAO BLIND RECRUITMENT - 후보키

benjykim 2021. 1. 11. 17:07
반응형

2020 KAKAO BLIND RECRUITMENT - 후보키

url : https://programmers.co.kr/learn/courses/30/lessons/42890

고민을 많이 했지만 마땅한 답이 떠오르지 않은 문제. 특히 2차원 배열이 주어지고 각 열에 대한 요소들만을 묶는 로직을 구현하는 것이 조금 막막했다. 말로 설명하려니 어색하다. 글로 다시 정리해보자.

  • 내가 생각하기에 깔끔한 코드

    from itertools import combinations
    
    def solution(relation):
        row = len(relation)
        col = len(relation[0])
    
        # 전체 조합
        candidates = []
        for i in range(1, col + 1):
            candidates.extend(combinations(range(col), i))
    
        # 유일성
        unique = []
        for candidate in candidates:
            tmp = [tuple([item[i] for i in candidate]) for item in relation]
            if len(set(tmp)) == row:
                unique.append(candidate) 
        # 최소성
        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)
    
    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"]]))
    
    [출처] https://whwl.tistory.com/104
    • 위의 코드에서 다음 두 부분이 제일 아름답다고 생각했다.

        # 1. extend 사용 및 combinations와 range 조합
        candidates.extend(combinations(range(col), i))
      
        # 2. list comprehension의 쓰임
        tmp = [tuple([item[i] for i in candidate]) for item in relation]
    • tmp라는 변수를 출력했을 때 다음과 같이 출력된다.

      # 원소가 1개인 경우
      tmp  =  [('100',), ('200',), ('300',), ('400',), ('500',), ('600',)]
      tmp  =  [('ryan',), ('apeach',), ('tube',), ('con',), ('muzi',), ('apeach',)]
      tmp  =  [('music',), ('math',), ('computer',), ('computer',), ('music',), ('music',)]
      tmp  =  [('2',), ('2',), ('3',), ('4',), ('3',), ('2',)]
      
      # 원소가 2개인 경우
      tmp  =  [('100', 'ryan'), ('200', 'apeach'), ('300', 'tube'), ('400', 'con'), ('500', 'muzi'), ('600', 'apeach')]
      tmp  =  [('100', 'music'), ('200', 'math'), ('300', 'computer'), ('400', 'computer'), ('500', 'music'), ('600', 'music')]
      tmp  =  [('100', '2'), ('200', '2'), ('300', '3'), ('400', '4'), ('500', '3'), ('600', '2')]   
      tmp  =  [('ryan', 'music'), ('apeach', 'math'), ('tube', 'computer'), ('con', 'computer'), ('muzi', 'music'), ('apeach', 'music')]
      tmp  =  [('ryan', '2'), ('apeach', '2'), ('tube', '3'), ('con', '4'), ('muzi', '3'), ('apeach', '2')]
      tmp  =  [('music', '2'), ('math', '2'), ('computer', '3'), ('computer', '4'), ('music', '3'), ('music', '2')]
      
      # 원소가 3개인 경우
      tmp  =  [('100', 'ryan', 'music'), ('200', 'apeach', 'math'), ('300', 'tube', 'computer'), ('400', 'con', 'computer'), ('500', 'muzi', 'music'), ('600', 'apeach', 'music')]
      tmp  =  [('100', 'ryan', '2'), ('200', 'apeach', '2'), ('300', 'tube', '3'), ('400', 'con', '4'), ('500', 'muzi', '3'), ('600', 'apeach', '2')]
      tmp  =  [('100', 'music', '2'), ('200', 'math', '2'), ('300', 'computer', '3'), ('400', 'computer', '4'), ('500', 'music', '3'), ('600', 'music', '2')]
      tmp  =  [('ryan', 'music', '2'), ('apeach', 'math', '2'), ('tube', 'computer', '3'), ('con', 'computer', '4'), ('muzi', 'music', '3'), ('apeach', 'music', '2')]
      
      # 원소가 4개인 경우
      tmp  =  [('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차원 배열이 주어졌을 때, 각 행의 첫 번째 원소들만 가져와 리스트로 만드는 로직은 다른 코딩 테스트를 볼 때에도 도움이 될 것 같다.

반응형