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

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차원 배열이 주어졌을 때, 각 행의 첫 번째 원소들만 가져와 리스트로 만드는 로직은 다른 코딩 테스트를 볼 때에도 도움이 될 것 같다.