[프로그래머스][Lv.2] 의상 | python3

문제링크:  의상

---

문제설명

코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.

예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다.

종류   이름
얼굴   동그란 안경, 검정 선글라스
상의   파란색 티셔츠
하의   청바지
겉옷   긴 코트

코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
코니는 하루에 최소 한 개의 의상은 입습니다.

코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한조건

- clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
- 코니가 가진 의상의 수는 1개 이상 30개 이하입니다.
- 같은 이름을 가진 의상은 존재하지 않습니다.
- clothes의 모든 원소는 문자열로 이루어져 있습니다.
- 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.

---

 

문제풀이

딕셔너리로 각 종류의 옷과 갯수를 저장한다.

하나만 입어도 되니까 계산은 (갯수+1)로 계산. 전부 0일 경우만 마지막에 빼주면 됨.

 

나의코드

def solution(clothes):
    answer = 1
    clothes_dic={}
    for cloth in clothes:
        if cloth[1] in clothes_dic:
            clothes_dic[cloth[1]]+=1
        else:
            clothes_dic[cloth[1]]=1
            
    for key in clothes_dic.keys():
        # 하나만 입으면 되기때문에 아무것도 선택안한 경우도 추가해서 계산.
        answer*=(clothes_dic[key]+1)
    return answer-1 # 아무것도 안입은 경우

 

---

 

참고하기

def solution(clothes):
    from collections import Counter
    from functools import reduce
    cnt = Counter([kind for name, kind in clothes])
    answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
    return answer

---

🔹 코드 분석

def solution(clothes):
    from collections import Counter  # 1️⃣ 개수 세기 위한 Counter 모듈 불러오기
    from functools import reduce  # 2️⃣ 누적 연산을 위한 reduce 함수 불러오기

---

    cnt = Counter([kind for name, kind in clothes])  # 3️⃣ 의상 종류별 개수 세기

• clothes는 (의상 이름, 의상 종류) 형태의 리스트입니다.
  예를 들어:

  clothes = [("yellow_hat", "headgear"), 
             ("blue_sunglasses", "eyewear"), 
             ("green_turban", "headgear")]
  

• 의상의 종류만 모아서 리스트로 만들고, Counter를 사용해 개수를 셉니다.

  cnt = Counter(["headgear", "eyewear", "headgear"])
  

  결과:

  Counter({'headgear': 2, 'eyewear': 1})
  

  → "headgear"는 2개, "eyewear"는 1개.

---

🔹 cnt.values() 와 1의 역할

answer = reduce(lambda x, y: x * (y + 1), cnt.values(), 1) - 1

 

---

✅ cnt.values()는 뭐야?

cnt = Counter({'headgear': 2, 'eyewear': 1})
cnt.values()  # [2, 1]

• Counter 객체의 .values()는 의상 종류별 개수만 리스트 형태로 반환해.
• 즉, cnt.values()는 [2, 1]처럼 각 의상 종류별 개수의 리스트가 됨.

---

✅ 1의 역할 (초기값)

reduce(lambda x, y: x * (y + 1), cnt.values(), 1)

• reduce()는 리스트의 값을 누적 연산하는 함수야.
• reduce(함수, 리스트, 초기값) 형태로 사용됨.
• 1은 초기값으로, 곱셈 연산을 하므로 1을 시작값으로 줌.

---

✅ 계산 과정 예제

예를 들어, 의상 종류별 개수가:

cnt = {'headgear': 2, 'eyewear': 1}
cnt.values() = [2, 1]

이제 reduce()를 사용하여 조합을 계산해볼게.

📌 1단계: 각 의상 종류별 (개수 + 1) 계산

• "headgear" → 2개 + 안 입는 경우(1) = 3가지
• "eyewear" → 1개 + 안 입는 경우(1) = 2가지

즉,

cnt.values()  # [2, 1]
(y + 1) 적용  # [3, 2]

📌 2단계: reduce()로 곱하기

• 초기값 1에서 시작
• reduce(lambda x, y: x * (y + 1), [2, 1], 1)

연산 과정:

1 * (2 + 1)  = 1 * 3 = 3
3 * (1 + 1)  = 3 * 2 = 6

결과 → 6

---

✅ 최종 정리

• cnt.values() → 의상 종류별 개수 리스트 [2, 1]
• (y + 1) → 각 종류별 (개수 + 1)
• reduce() → 모든 경우의 수를 곱함 ((2+1) * (1+1) = 6)
• -1 → 아무것도 안 입는 경우 제거

✔️ 최종적으로 서로 다른 의상 조합 개수가 반환됨! 

---

🔥 코드의 핵심 아이디어

1. 의상 종류별 개수를 Counter로 계산 → O(N)
2. 각 종류별 (개수 + 1) 값을 곱한 후, 전체 경우의 수에서 1을 빼기 → O(N)
3. 시간 복잡도: O(N) → 매우 효율적!

✔️ 수학적 원리를 활용한 최적의 조합 계산 코드! 🚀