프로그래머스: [위장]

📌 프로그래머스: [위장]

🔗 문제 링크

---

문제 설명 📄

각 의상의 종류별로 한 개씩 착용할 수 있으며, 최소 하나 이상의 의상을 선택해야 한다.
같은 종류의 의상을 여러 개 소유할 수 있지만, 같은 종류에서 한 개만 선택 가능하다.
의상의 조합 수를 구하는 문제.

---

문제 접근 방식 💡

• 의상의 종류별로 개수를 세고 조합을 계산해야 한다.
• 특정 종류의 의상을 착용하는 경우의 수는 (해당 종류 개수 + 1)이다. (선택하지 않는 경우 포함)
• 따라서, 모든 종류의 의상을 곱한 값에서 1을 빼면 총 조합 개수가 된다. (모든 의상을 선택하지 않는 경우 제외)

---

Solution 💻

from collections import defaultdict

def solution(clothes):
    pattern = defaultdict(list)
    
    for clothe in clothes:
        pattern[clothe[1]].append(clothe[0])
    
    answer = 1
    for i in pattern.values():
        answer *= (len(i) + 1)
    
    return answer - 1

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(N),
  • N은 의상의 개수.
  • 해시맵(Dictionary)에 의상 정보를 저장 (O(N))
  • 종류별로 개수를 계산하여 곱셈 연산 (O(K), K는 의상 종류 개수)
  • 전체적으로 O(N + K) ≈ O(N)

공간 복잡도 분석 🗄️

• 공간 복잡도: O(K),
  • K는 의상 종류 개수.
  • defaultdict에 의상 정보를 저장하는데, 최대 K개의 키만 필요.

---

리팩토링 🛠️

from collections import Counter

def solution(clothes):
    count = Counter([kind for _, kind in clothes])
    answer = 1
    for c in count.values():
        answer *= (c + 1)
    return answer - 1

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(N),
  • Counter()를 이용해 한 번의 순회로 종류별 개수를 세므로 효율적.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(K),
  • 의상의 종류 개수만큼 저장.