[해시] 프로그래머스 위장 문제 파이썬(python)

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

맞았습니다:

from itertools import combinations
def solution(clothes):
    count={}
    for i in clothes:
        if i[1] in count:
            count[i[1]] += 1
        else:
            count[i[1]] = 1
    total = 1
    keys = list(count.keys())
    types = len(keys)

    for key in keys:
        total *= count[key]+1
    total -= 1
    return total

✔︎ 분명 어제 Counter함수를 새로 배웠는데 적용을 못했다.

Counter(배열) → 배열 안에 각 원소가 몇 개 들어있는지를 < key=원소이름, value=들어있는개수 > 의 dictionary 반환.

맨 첫번째 for문은 이를 직접 구현한 것이다.

Counter 함수를 썼다면, 

clothes 배열안의 옷의 종류(각 안쪽 리스트들의 두번째 원소)들만 뽑아서 새로운 배열을 함수의 인자로 주어야 한다.

Counter( [ kind for name, kind in clothes ] )

 [ kind for name, kind in clothes ] 는 clothes의 [name, kind] 즉 안 쪽의 리스트 중에서도 그 두번째 원소 kind만 뽑아서 배열로 만든 list comprehension

 

✔︎ 각 옷의 종류(count의 key)가 몇개(count의 value) 들어있는지 파악을 했다면, 

해당 종류의 옷의 개수(value)에 1을 더해준 값을 모두 곱해준다.

1을 더해주는 것은, 해당 옷의 종류를 입지 않는 경우를 포함한 것이다.

그렇게 하면 어떤 종류는 입고 어떤 종류는 안 입고 모든 경우의 수가 고려된다.

단, 전부 안 입는 경우까지 포함되게 되므로 마지막에 1을 빼준다.

 

---

< cf > 시간초과 1:

def solution(clothes):
    count={}
    for i in clothes:
        if i[1] in count:
            count[i[1]] += 1
        else:
            count[i[1]] = 1
    total = 0
    keys = list(count.keys())
    types = len(keys)
    for i in range(1, (2**types-1)+1):  # 1 ~ 2^n-1 (n = 의상 종류의 수)
        case = bin(i)[2:].rjust(types, '0') #'0b~'형태의 이진수 문자열로 반환하므로, 접두어 0b만 제외
        result = 1
        for i in range(len(case)):
            if case[i] == '1':   #이진수 해당 자릿수가 1이라면, 스파이가 오늘 입는 종류.
                result *= count[keys[i]]
        total += result
        
    return total

'어떤 종류는 입고 어떤 종류는 안입고'를 이진수로 표현했다.

예를 들어 옷의 종류가 4가지라 하면,

해당 종류를 입는 경우는 1, 안 입는 경우는 0으로 보고,

0000 부터 1111 까지 2진수 (10진수로는 2^4가지)로 표현하였다.

만약 count = {'headgear':2, 'eyewear':1, 'top': 3, 'shoes': 1} 이고,

for문으로 i를 0000 부터 1111까지 돌렸을 때 

i 가 0110 인 경우, eyewear과 top만 입어 1*3을 더해주는 것이다.

 

✔︎10진수 → 2진수로 표현하는 법:

bin(5)  → '0b101' 

즉 0b가 접두어로 붙은 문자열로 반환해준다.

(.rjust()는 문자열을 오른쪽 정렬시켜준다, til 220409 참고)

 

 

< cf > 시간초과 2:

from itertools import combinations
def solution(clothes):
    count={}
    for i in clothes:
        if i[1] in count:
            count[i[1]] += 1
        else:
            count[i[1]] = 1
    total = 0
    keys = list(count.keys())
    types = len(keys)
    
    for i in range(1, types+1):
        caselist = combinations(count, i)
        for combi in caselist:
            result = 1
            for type in combi:
                result *= count[type]
            total += result
        
    return total

위에랑 논리는 같은데 다만 이진수로 풀어내지 않고,

조합을 써서 리스트로 새로 받아온 다음 그 리스트 안의 각 튜플(가능한 조합) 안의 옷의 종류(count 의 key)에 해당하는 옷의 개수(count의 value)를 곱해주고 각각을 더한 것.

✔︎ itertools라이브러리의 combinations()함수 - til 220409 참고

 

 

➕ 다른 사람 풀이:

-from functools import reduce

참고: https://heytech.tistory.com/49

reduce 함수 사용 → "반복 가능한 객체(iterable object) 내 각 요소를 연산한 뒤 이전 연산 결과들과 누적해서 반환해 주는 함수"

reduce(연산함수, 반복가능객체, [초기값])

위 연산함수부분에는 lambda x,y:x*(y+1)

반복가능객체에는 count.values(),

초기값(원래는 생략가능)에는 1을 넣어주면,

count.values()가 [2, 3, 4]라고 쳤을 때

((1*(2+1))*(3+1))*(4+1)을 리턴해준다.