[알고리즘/Python] 프로그래머스 - 위장 (해시)

프로그래머스 문제

 

서로 다른 옷의 조합의 수 구하는 법 👀

여러 의상끼리의 조합을 구하는 것이므로 곱집합을 생각했다.

 

곱집합 (데카르트 곱)은 각 집합의 원소를 각 성분으로 하는 튜플들의 집합으로 A x B 라고 한다. 곱집합의 개수는 간단하게 A x B 로 계산할 수 있다.

 

해당 문제에서는 자기 자신만을 갖는 경우도 포함되어야 하기 때문에 (A+1) x (B+1) - 1 로 계산했다. 1 을 빼주는 이유는 (A+1) x (B+1) 의 경우에는 비어있는 경우도 포함되기 때문이다.

기존 리스트 = [a], [b], [c]
최종 결과 = [a], [b], [c], [a, b], [a, c], [b, c], [a, b, c]

 

풀이1 (시간초과)

solution 함수

• clothes : 스파이가 가진 의상들이 담긴 2차원 배열
• return : 서로 다른 옷의 조합의 수

1. Key: 종류, Value: 이름 으로 Dictionary 만들기
   • 자기 자신만 포함하는 경우도 계산해야하기 때문에 0 을 포함했다.
2. 곱집합 개수 구하기
   • 개수를 어떻게 구할지 몰라서 itertools.product 함수로 전체 케이스를 구했더니 시간초과가 되었다.

from itertools import product

def solution(clothes):

    # Key: 종류, Value: 이름 으로 Dictionary 만들기 
    clothes_dict = {}
    for c in clothes:
        key = c[1]
        if not key in clothes_dict:
            clothes_dict[key] = [0]
        clothes_dict[key].append(c[0])
        
    # 개수 구하기
    cases = len(list(product(*clothes_dict.values()))) - 1
    return cases

풀이2 (통과 풀이)

• 시간초과를 해결하기 위해 모든 케이스를 구하지 않고 개수만 계산하는 방식으로 변경했다.
  • 하나씩 입는 경우도 포함하기 위해 1 을 더한다.
  • 곱집합(?) 개수 = (A+1) * (B+1) - 1
• dict value 리스트에 0 을 추가했던 걸, 개수에서 1 을 더해주는 방식으로 바꿨다.

def solution(clothes):

    # Key: 종류, Value: 이름 으로 Dictionary 만들기
    clothes_dict = {}
    for c in clothes:
        key = c[1]
        if not key in clothes_dict:
            clothes_dict[key] = []
        clothes_dict[key].append(c[0])
    
    # 개수 구하기
    cases = 1
    for v in clothes_dict.values():
        cases *= len(v) + 1
    return cases - 1

 

풀이3 (Counter 이용)

• 다른 분들의 풀이를 보고 Counter 를 이용해봤다.
• collections.Counter 를 이용해서 각 종류마다 개수만 저장한다.
• 라이브러리를 통해 개수를 세는 과정이 있어서 그런지 풀이 2 보다 시간은 오래 걸렸다.

from collections import Counter

def solution(clothes):

    # Key: 종류, Value: 개수로 Dictionary 만들기 
    count = Counter([kind for name, kind in clothes])
    
    # 곱집합 개수 구하기
    cases = 1
    for v in count.values():
        cases *= v + 1
    return cases - 1

Counter 클래스를 통해 만들어진 count 변수는 다음과 같다.

clothes = [
	["yellowhat", "headgear"], 
	["bluesunglasses", "eyewear"], 
	["green_turban", "headgear"]
]

Counter({'headgear': 2, 'eyewear': 1}

 

 

✔︎ 풀이 2 정확성 테스트

테스트 1 〉	통과 (0.02ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.01ms, 10.2MB)
테스트 4 〉	통과 (0.02ms, 10MB)
테스트 5 〉	통과 (0.01ms, 10.1MB)
테스트 6 〉	통과 (0.01ms, 10.2MB)
테스트 7 〉	통과 (0.02ms, 10.1MB)
테스트 8 〉	통과 (0.01ms, 10.2MB)
테스트 9 〉	통과 (0.01ms, 10.2MB)
테스트 10 〉	통과 (0.01ms, 10.1MB)
테스트 11 〉	통과 (0.01ms, 10.2MB)
테스트 12 〉	통과 (0.02ms, 10.2MB)
테스트 13 〉	통과 (0.02ms, 10.2MB)
테스트 14 〉	통과 (0.01ms, 10.2MB)
테스트 15 〉	통과 (0.01ms, 10.2MB)
테스트 16 〉	통과 (0.01ms, 10.2MB)
테스트 17 〉	통과 (0.01ms, 10.3MB)
테스트 18 〉	통과 (0.01ms, 10.2MB)
테스트 19 〉	통과 (0.01ms, 10.2MB)
테스트 20 〉	통과 (0.01ms, 10.2MB)
테스트 21 〉	통과 (0.01ms, 10.2MB)
테스트 22 〉	통과 (0.01ms, 10.2MB)
테스트 23 〉	통과 (0.01ms, 10.2MB)
테스트 24 〉	통과 (0.01ms, 10.2MB)
테스트 25 〉	통과 (0.01ms, 10.2MB)
테스트 26 〉	통과 (0.02ms, 10.2MB)
테스트 27 〉	통과 (0.01ms, 10.2MB)
테스트 28 〉	통과 (0.02ms, 10.2MB)

✔︎ 풀이 3 정확성 테스트

테스트 1 〉	통과 (0.05ms, 10.2MB)
테스트 2 〉	통과 (0.04ms, 10.2MB)
테스트 3 〉	통과 (0.04ms, 10.2MB)
테스트 4 〉	통과 (0.05ms, 10.1MB)
테스트 5 〉	통과 (0.03ms, 10.2MB)
테스트 6 〉	통과 (0.03ms, 10.1MB)
테스트 7 〉	통과 (0.04ms, 10.2MB)
테스트 8 〉	통과 (0.04ms, 10.2MB)
테스트 9 〉	통과 (0.03ms, 10.2MB)
테스트 10 〉	통과 (0.03ms, 10.2MB)
테스트 11 〉	통과 (0.03ms, 10.2MB)
테스트 12 〉	통과 (0.04ms, 10.2MB)
테스트 13 〉	통과 (0.04ms, 10.1MB)
테스트 14 〉	통과 (0.04ms, 10.2MB)
테스트 15 〉	통과 (0.03ms, 10.2MB)
테스트 16 〉	통과 (0.03ms, 10.2MB)
테스트 17 〉	통과 (0.03ms, 10.3MB)
테스트 18 〉	통과 (0.04ms, 10.2MB)
테스트 19 〉	통과 (0.04ms, 10.2MB)
테스트 20 〉	통과 (0.03ms, 10.2MB)
테스트 21 〉	통과 (0.03ms, 10.1MB)
테스트 22 〉	통과 (0.03ms, 10.2MB)
테스트 23 〉	통과 (0.04ms, 10.2MB)
테스트 24 〉	통과 (0.04ms, 10.2MB)
테스트 25 〉	통과 (0.04ms, 10.3MB)
테스트 26 〉	통과 (0.04ms, 10.1MB)
테스트 27 〉	통과 (0.04ms, 10.3MB)
테스트 28 〉	통과 (0.05ms, 10.2MB)

---

programmers.co.kr/learn/courses/30/lessons/42578

코딩테스트 연습 - 위장