📌 프로그래머스: [위장]
🔗 문제 링크
문제 설명 📄
각 의상의 종류별로 한 개씩 착용할 수 있으며, 최소 하나 이상의 의상을 선택해야 한다.
같은 종류의 의상을 여러 개 소유할 수 있지만, 같은 종류에서 한 개만 선택 가능하다.
의상의 조합 수를 구하는 문제.
문제 접근 방식 💡
- 의상의 종류별로 개수를 세고 조합을 계산해야 한다.
- 특정 종류의 의상을 착용하는 경우의 수는 (해당 종류 개수 + 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),
- 의상의 종류 개수만큼 저장.
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| 프로그래머스: [전력망을 둘로 나누기] (0) | 2025.03.08 |
|---|---|
| 프로그래머스: [베스트앨범] (0) | 2025.03.08 |
| 프로그래머스 [양궁대회] (0) | 2025.03.06 |
| 프로그래머스 [이모티콘 할인 행사] (0) | 2025.03.05 |
| 프로그래머스 [[PCCP 기출문제] 2번 / 퍼즐 게임 챌린지] (0) | 2025.03.04 |