프로그래머스 위장

테스트 1에 대해 시간 초과난 코드.

def solution(clothes):
    c_dict = {}
    for c in clothes:
        if c[1] in c_dict:
            c_dict[c[1]] += 1
        else:
            c_dict[c[1]] = 1
    c_list = []
    for i in c_dict:
        c_list.append(c_dict[i])
    result = 0
    length = len(c_list)
    n = 2 ** length
    for i in range(1, n):
        bin_n = format(i, 'b').zfill(length)
        multi_result = 1
        for j in range(length):
            num = int(bin_n[j])
            if num != 0:
                multi_result *= c_list[j] * num
        result += multi_result
    return result

바보같이 전체 경우의 수에서 하나도 안고른 경우를 빼면 되는건데... 삽질을 했다.

 

전체 경우의 수 - 1을 하면 된다.

모자가 3개, 바지가 4개라고 할 때,

모자의 경우 입지 않은 경우를 포함하면 4개다.

바지의 경우 입지 않은 경우를 포함하면 5개다.

총 나올 수 있는 조합은 4 x 5 = 20인데 여기서 하나도 입지 않는 경우는 빼야하므로 결국 19개의 경우가 나온다.

 

다시 푼 코드

def solution(clothes):
    c_dict = {}
    for c in clothes:
        if c[1] in c_dict:
            c_dict[c[1]] += 1
        else:
            c_dict[c[1]] = 1
    c_list = []
    length = 0
    for i in c_dict:
        length += 1
        c_list.append(c_dict[i])
    result = 1
    for j in c_list:
        result *= (j + 1)
    return result - 1

 

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

코딩테스트 연습 - 위장 | 프로그래머스