[2019 카카오 코딩테스트] 후보키 (파이썬3) / 자체 해설 및 풀이

 

 

 

지난 '오픈채팅방' 문제에 이어

2019 카카오 코딩테스트 '후보키' 문제를

파이썬으로 풀어봤다.

 

 

 

⬇ [알고리즘/심심풀이 문제풀기] - [2019 카카오 코딩테스트] 오픈채팅방 (파이썬3)

[2019 카카오 코딩테스트] 오픈채팅방 (파이썬3)

 

 

또다시 느끼는 건 파이썬은 정말 

알고리즘 풀기 좋은 언어이다.

 

주석을 뺀 순수 라인수가 26줄!!

정말 말이 안 된다.

 

 

 

 

 

 

 

코딩테스트 연습 - 후보키 | 프로그래머스

 

 

 

---

 

자체 해설

 

 

막연하지만 차근차근 정리해 보기로 했다.

내 방법은 반복문이 너무 많아서 사실 좋은 방법 같아 보이진 않지만

아래와 같은 제한사항이 있기에 마음 놓고 코드를 써 내려갔다.

 

• relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
• relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
• relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.

 

 

유일성 :

1. 2차원 배열로 들어온 relation[row][col]의 값 중 col이 같은 값을 하나의 set에 넣어서 검증하면 된다고 생각했다.
2. 여러 col의 조합이 유일한지 확인하기 위해서는 인위적인 조작이 필요하다고 생각했다.
3. 컴럼들의 경우의 수를 모두 얻은 후에 각 값들의 유일성을 검증하기로 했다.
4. itertools의 combinations를 사용해서 col의 모든 조합을 만든다.
5. 반복문으로 col의 조합을 가져와서 합친 쳐서 하나의 tempCol을 만들고 set에 넣어서 개수를 확인한다.
     ex) 1,2 조합이라면 set(["100ryan","200apeach","300tube","400con","500muzi","600apeach"])
6. 개수가 원래 row의 수와 동일하면 유일성이 보장된 것이기 때문에 따로 저장해둔다.

 

최소성 : 

1. 유일함이 보장된 조합에서 최소성을 검증한다.
2. 리스트 내에서 부분집합을 갖고 있다면 최소성 조건에 맞지 않기 때문에 삭제 대상 set에 넣는다.
3. 유일성이 보장된 그룹의 수에서 삭제 대상의 수를 뺀다.

 

 

 

 

 

 

 

작성 코드

from itertools import combinations
def solution(relation):
    answer = 0
    # 모든 컬럼의 조합 리스트
    all = list()

    #유일성 만족하는 조합 리스트
    uniqeIndex = []

    if len(relation) > 0:
        # 컬럼의 개수
        colSize = len(relation[0])
        # 로우의 개수
        rowSize = len(relation)

        # 모든 컬럼의 조합 구하기 (Set형태)
        for i in range(1, colSize + 1):
            # append는 런타임에러가 뜸 append와 extend 비교하여 알아둘 것
            all.extend([set(k) for k in combinations([j for j in range(colSize)], i)])

        # 조합들의 유일성 검증
        for comb in all:
            #set에 추가하여 사이즈 비교로 검증
            vaildSet = set()
            # 조합에 해당되는 로우를 하나의 str로 합쳐서 set에 넣음
            for row in range(rowSize):
                temp = ''
                for col in comb:
                    temp += relation[row][col]
                vaildSet.add(temp)
            # 유일성 확인하여 리스트에 추가
            if len(vaildSet) == rowSize:
                uniqeIndex.append(comb)

        # 최소성 검증
        # 삭제대상 Set (최소성 위배)
        delSet = set()
        #부분집합 여부 확인
        for stdMinElem in uniqeIndex:
            for idx, compMinElem in enumerate(uniqeIndex):
                # 부분집합이면서 자기 자신이 아니라면 상위집합을 삭제 대상에 추가
                if stdMinElem.issubset(compMinElem) and stdMinElem != compMinElem:
                    delSet.add(uniqeIndex.index(compMinElem))
        # 유일성 - 최소성 위배
        answer = len(uniqeIndex)-len(delSet)
    return answer

 

 

카카오 공식 해설 : https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/

 

 

 

---

 

 

도움이 되셨다면

로그인이 필요 없는 공감 버튼 꾹 눌러주세요!