프로그래머스: #해시, 위장

문제

---

스파이가 가지고 있는 옷을 번갈아가면서 입으려고 한다. 

이 옷들을 번갈아 가면서 입을 수 있는 경우의 수를 구하기

 

제한사항

clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
같은 이름을 가진 의상은 존재하지 않습니다.
clothes의 모든 원소는 문자열로 이루어져 있습니다.
모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
스파이는 하루에 최소 한 개의 의상은 입습니다.

 

입출력 예제

clothes = [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]     : 5
clothes = [["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]]                              : 3

 

첫 번째의 경우 headgear에 해당하는 의상이 yellow_hat, green_turban 두 가지이고,

eyewear에 해당하는 의상이 blue_sunglasses 한가지 이므로

하나씩 착용하는 경우 3가지, 각 경우별로 교차로 착용하는 경우가 2가지 이므로 총 5가지가 정답

 

풀이

---

첫 번째 풀이 (오답)

def solution(clothes):
    my_dic = dict()
  
    # { 의상 : 의상 수 } 형태를 만드는 과정
  
    for i in clothes:
        wear = i[1]
        if wear in my_dic.keys() :
            my_dic[wear] += 1
        else:
            my_dic[wear] = 1
    
    # 인덱싱을 이용한 조합의 경우 구하기 
    temp = list(my_dic.values())
    answer = 0
    for i in range(1,len(temp)+1):
        for n in range(0,len(temp)):
            if n+i > len(temp):
                break
            answer += np.prod(temp[n:n+i]) 

 

NOTE

접근법으로 우선 dictionary 형태로 { 의상 : 의상 수 } 를 만들어 놓은 뒤에
의상수의 숫자를 이용해서 Combination을 이용하려 했다.

그래서 조합으로 가능한 경우의 수를 저렇게 아래처럼 일일이 인덱싱을 이용해서 추출하는데는 성공했다.

그 결과가 list 값으로 나오기 때문에 list의 원소들을 numpy의 prod를 이용해서 모두 곱해서 
answer 변수에 누적시켜 값을 return 했으나
예제는 모두 통과했지만 test 에서는 3/4 가량이 오답으로 나왔다.

temp = [3,4,2]
for i in range(1,len(temp)+1):
    for n in range(0,len(temp)):
        if n+i > len(temp):
            break
        print(temp[n:n+i]) 

# print 결과
[3]
[4]
[2]
[3, 4]
[4, 2]
[3, 4, 2]

 

그러던 중에 조합으로 가능한 모든 경우의 수는

---

(원소의 수 + 1) 을 한 값을 모두 곱한 뒤 - 1

---

을 한 값과 같다는 사실을 발견했다. 
( 1을 빼주는 이유는 아무것도 선택되지 않은 경우를 제외하기 위함이다. )

즉, 이 문제의 경우에서 의상이 A, B, C 3개일 때,
총 조합의 수 = (n(A)+1)(n(B)+1)(n(C)+1) - 1

 

두 번째 풀이 (정답)

def solution(clothes):
    
    my_dic = dict()
    
    for i in clothes:
        wear = i[1]
        if wear in my_dic.keys() :
            my_dic[wear] += 1
        else:
            my_dic[wear] = 1
            
    answer=1
    for key in my_dic:
        answer *= (my_dic[key]+1)
        
    return (answer - 1)

 

 

NOTE

여기에서 나는 dictionary에서 key값이 있는지 확인해서 일일이 Count를 해주었지만
아래와 같이 collections의 Counter를 사용하면 조금더 간단한 코드로 원소의 갯수를 추출할 수 있다.

 

def solution(clothes):
    from collections import Counter
    my_dic = Counter([clo for _,clo in clothes])
            
    answer=1
    for key in my_dic:
        answer *= (my_dic[key]+1)
        
    return (answer - 1)