[Programmers_Python] 위장

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

프로그래머스

내 풀이 방식 -> 시간 초과

• 옷 종류별로 몇개가 있는지를 나타내기 위해 dictionary 자료구조를 이용했다.
• 하나 이상의 옷 종류를 고르는 모든 경우의 수를 옷 종류의 개수로 표현해서 리스트를 만든다.
• 아래의 사진은 테스트 케이스에 대해 실행해서 나온 결과이다. 출력 부분에 dictionary와 dictionary의 value들, 모든 경우의 수를 표현한 리스트를 출력한 결과이다.

• 모든 경우의 리스트 내부의 각 튜플들의 원소들의 곱을 다 더해서 정답을 구했다.

import itertools

def multiply(lst):
    ans = 1
    for k in lst:
        ans *= k
    return ans

def solution(clothes):
    dic = dict()
    for i in range(len(clothes)):
        if clothes[i][1] in dic.keys():
            dic[clothes[i][1]] += 1
        else:
            dic[clothes[i][1]] = 1
    lst = list(dic.values())
    answer_lst = []
    answer = 0
    for i in range(len(dic.values())):
        answer_lst.extend(list(itertools.combinations(lst, i+1)))
    print(answer_lst)
    for i in range(len(answer_lst)):
        answer += multiply(answer_lst[i])
    return answer

 이런 방식으로 문제를 푸니 채점 결과에서 1개가 시간 초과가 떴다;; 

 

정답 코드

• 내 방식과 동일하게 dictionary 자료구조를 이용한다.
• 여기서 각 옷 종류의 개수를 1개가 더 있다고 생각해서 푼다. ( A라는 종류에 a, b라는 옷이 있으면 a입기, b입기, 안입기 이렇게 3가지의 경우가 있다고 생각)
• 각 옷 종류의 개수를 모두 곱해서 그 값에서 -1을 해준다. (모든 옷을 안입는 경우를 뺀다.)

def solution(clothes):
    dic = dict()
    for i in range(len(clothes)):
        if clothes[i][1] not in dic:
            dic[clothes[i][1]] = 1
        else:
            dic[clothes[i][1]] += 1
    lst = list(dic.values())
    answer = 1
    for k in lst:
        answer *= (k+1)
    return answer - 1

이러한 방식으로 풀면 시간 초과가 뜨지 않는다. 단순한 경우의 수 문제??를 풀듯이 접근을 했으면 간단하게 풀리는 걸 너무 복잡하게 생각한거 같다,,,,