[프로그래머스] 위장

[문제]

코딩테스트 연습 - 위장

 

 

---

 

[풀이]

-시행착오-

코테 때와는 다르게 어떤 타입의 문제인지 미리 알 수 있는 상태였고 hash 유형이니까 별생각 없이 주어진 clothes 리스트를 가공하여 {의상 종류: 의상 이름} 형태로 딕셔너리를 만들어 놓고 풀어가려고 시도했던 것이 화근이 되었다.

이렇게 생각없이 딕셔너리부터 만들어 놓은 뒤에 진행된 사고의 흐름은 다음과 같았다.

 

1. 적어도 하나의 의상은 입어야 한다는 제한사항이 있네!
2. 특정 의상 타입 가운데 하나의 의상을 선택해 시작 의상으로 설정하고 나머지 타입들에 해당하는 의상을 넣거나 넣지 않거나 해서 의상 요소들을 저장하면서 중복된 의상들의 경우는 제거하면 ([파랑 안경, 검정 티, 빨강바지]와 [검정 티, 빨강바지, 파랑 안경]은 순서는 바뀌었지만 동일한 요소로 간주하여 하나만 남기도록 처리)
3. 마지막에 남은 요소들의 갯수가 정답이 되겠다.

 

위의 로직에서 2번 과정을 수행하기 위해 딕셔너리의 모든 요소들 간에 product 연산을 했는데 이는 시간복잡도를 많이 높이는 원인이 되었으며 중복 원소를 제거하는 로직 수행 과정 중에 데이터를 tuple -> list -> tuple 형태로 변환한다거나 하는 비효율 적인 알고리즘이 되고 말았다. 통상 해시 알고리즘을 사용하는 경우는 효율성을 테스트하기 위해 시간복잡도 제한이 엄격하게 걸리는 경우가 많은걸 생각해볼 때 상당히 좋지 않은 알고리즘이 작성된 것이다.

 

부끄럽지만 다시는 같은 실수를 반복하지 않기위해 위의 로직을 박제해 놓는다.

중요한 것은 큰 낭패를 볼 수 있으므로 절대 짐작하여 데이터를 미리 가공해 놓으면 안된다는 것이다.

반드시 차분히 요구사항과 입출력을 분석하여 알고리즘의 뼈대가 잡혔을 때 구현을 시작해야한다.

from itertools import product


def solution_fail(clothes):
    answer = 0
    clothes_dict = dict()
    for c in clothes:
        try:
            temp_cloths = clothes_dict[c[1]]
            clothes_dict.setdefault(c[1], temp_cloths.append(c[0]))
        except KeyError:
            clothes_dict.setdefault(c[1], [c[0]])
    # print(clothes_dict)
    all_clothes = []
    clothes_set = set()
    for key in clothes_dict.keys():
        all_clothes.clear()
        another_keys = []
        for k in clothes_dict.keys():
            another_keys.append(k)
        another_keys.remove(key)

        # 현재 key에 해당하는 복장의 리스트를 생성한다.
        all_clothes.append(clothes_dict[key])

        # 다른 key들에 해당하는 복장의 리스트 들을 생성하되 공백 요소를 포함하여 생성한다.
        for another_key in another_keys:
            another_clothes = clothes_dict[another_key]
            another_clothes.append('')
            all_clothes.append(another_clothes)

        try:
            all_clothes[0].remove('')
        except:
            pass

        for elem in product(*all_clothes):
            elem = list(elem)
            elem.sort()
            elem = tuple(elem)
            clothes_set.add(elem)
    try:
        clothes_set.remove(('', '', ''))
    except KeyError:
        pass
    return len(clothes_set)

 

 

-재도전-

다음과 같이 의상이 주어진다고 해보자.

의상 종류	의상 이름
모자	야구모자, 중절모
안경	뿔테안경, 금테안경
신발	운동화, 구두

 

 

각 의상 종류별 의상 수를 CC라 하자

1. 먼저 생각해야 할 중요한 점은 의상을 선택하지 않을 수도 있다는 점이다. 즉, 야구모자를 선택했지만 안경과 신발은 착용하지 않을 수도 있다. 따라서 각 의상 종류별로 CC에 해당 의상 종류가 선택되지 않을 수 있는 경우의 수를 고려해 1을 더해준다.
2. 의상 종류별로 착용하는 것은 동시에 일어나는 사건이므로 각 종류의 CC를 모두 곱 연산해준다.
3. 마지막으로 주의할 점은 의상 종류 가운데 반드시 한 종류 이상은 착용해야 한다. 모두 착용하지 않는 경우의 수는 1가지뿐이다. 따라서 전체 경우의 수에서 모두 착용하지 않는 경우의 수 1을 빼준다. 

 

위의 로직을 코드로 옮기면 다음과 같다.

def solution(clothes):
    cloths_type = dict()

    # 각 의상 종류 별로 의상 수의 초기값을 1로 설정해 딕셔너리를 생성한다..
    # 초기값이 1인 이유는 각 의상 종류 별로 착용하지 않는 경우의 수가 있기 때문이다.
    for cloths in clothes:
        cloths_type.setdefault(cloths[1], 1)

    # 각 의상 종류 별로 의상 수를 더해준다.
    for cloths in clothes:
        temp_val = cloths_type[cloths[1]] + 1
        cloths_type[cloths[1]] = temp_val

    # 모든 의상 종류별로 동시에 착용 수있는 경우의 수를 구하는 것이므로 곱연산을 진행한다.
    result = 1
    for val in cloths_type.values():
        result *= val

    # 모든 경우에서 의상을 하나도 착용하지 않은 경우를 빼고 리턴한다.
    return result - 1

 

 

---

 

[개선]

python에서 hash가 필요할 때 강력하게 사용할 수 있는 것이 collections 패키지의 Counter 함수이다. Counter 함수는 ierable 객체를 인수로 받아 각 원소별로 갯수를 카운팅하여 Counter 객체로 반환해준다. Counter 객체는 dict의 서브타입으로 딕셔너리와 동일하게 key로 value(갯수)를 접근할 수 있다.

 

from collections import Counter


def solution(clothes):
    # Counter를 사용해서 의상 종류별 의상 수를 파악한다.
    cnt_by_cloths = Counter((cloths[1] for cloths in clothes))

    # 모든 의상 종류별로 동시에 착용 수 있는 경우의 수를 구하는 것이므로 곱연산을 진행한다.
    # 이 때 의상을 입지 않는 경우도 있으므로 각 의상 타입별로 (의상 수 + 1) 하여 곱연산 한다.
    ans = 1
    for key in cnt_by_cloths:
        ans *= cnt_by_cloths[key] + 1

    # 모든 경우에서 의상을 하나도 착용하지 않은 경우를 빼고 리턴한다.
    return ans - 1

이와 같이 hash가 필요할 때 Counter를 사용하면 가독성 좋은 코드를 만들 수 있다.

 

 

다음과 같이 collections.defaultdict()를 사용하여  풀 수도 있다.

from collections import defaultdict


def solution(clothes):
    clothes_dict = defaultdict(lambda: 1)
    for c in clothes:
        clothes_dict[c[1]] += 1
    
    # 동시 사건에 대한 경우의 수 = 곱연산.
    ans = 1
    for key in clothes_dict:
        ans *= clothes_dict[key]
    
    return ans - 1

defaultdict는 존재하지 않는 키에 접근할 경우 키: 미리 설정된 초기값 으로 딕셔너리 요소를 추가해주므로 일반 딕셔너리에 비해 편리하게 사용할 수 있다.