[프로그래머스] 해시 - 의상

안녕하세요. 탁입니다.

네번째 문제는 해시 유형의 Level2 문제인 '의상' 입니다.

의상

문제 설명

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

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

표

2열 × 4행

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

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

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

제한 사항

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

입출력 예

2열 × 2행

clothes	return
[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crowmask", "face"], ["bluesunglasses", "face"], ["smoky_makeup", "face"]]	3

입출력 예 설명

예제 #1

headgear에 해당하는 의상이 yellowhat, greenturban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

TypeScript

5 lines

1. yellow_hat
2. blue_sunglasses
3. green_turban
4. yellow_hat + blue_sunglasses
5. green_turban + blue_sunglasses

예제 #2

face에 해당하는 의상이 crowmask, bluesunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

TypeScript

3 lines

1. crow_mask
2. blue_sunglasses
3. smoky_makeup

나의 풀이

문제 접근 아이디어는 이랬습니다.

clothes를 의상의 종류별 몇 벌이 있는지로 만든 뒤에

(각 의상 종류별로 갖고 있는 벌수 + 1) 을 모두 곱한 뒤에 (안 입는 경우가 있기 때문에 +1 을 했음)

전부 곱해진 값에서 -1 을 한다. (최소 한개는 입어야해서 아예 안입는 경우는 없으므로)

$\prod_{i=1}^{n} (k_i + 1) - 1$

1. 초기화 상태

Python

3 lines

def solution(clothes):
    answer = 0
    return answer

2. 풀이 1: 풀이 과정

Python

9 lines

from collections import defaultdict
def solution(clothes):
    answer = 1 # 초기값을 1로 설정하여 값을 하나씩 곱해가도록
    dc = defaultdict(int) # 각 의상 종류별 개수를 세기 위해서 defaultdict() 선언
    for cloth in clothes:
        dc[cloth[1]] += 1 # 각 의상 종류별 개수 세기
    for n in dc.values(): # 각 의상 종류별 개수를 곱하기
        answer = answer * (n+1) # 안 입은 경우를 처리하기 위해 +1
    return answer - 1 # 전체 답안은 하나도 안입은 경우를 제외해서 -1

3. 풀이 1: 답안 확인

Python

9 lines

from collections import defaultdict
def solution(clothes):
    answer = 1
    dc = defaultdict(int)
    for cloth in clothes:
        dc[cloth[1]] += 1
    for n in dc.values():
        answer = answer * (n+1)
    return answer - 1

4. 풀이 2: 풀이 과정

Python

6 lines

from collections import Counter
def solution(clothes):
    answer = 1 # 초기값을 1로 설정하여 값을 하나씩 곱해가도록
    for l in list(Counter([j for i, j in clothes]).values()): # list(Counter()) 이용해서 각 의상 종류별 개수를 파악하고 바로 for문 진입
        answer = answer * (l+1) # 안 입은 경우를 처리하기 위해 +1
    return answer -1 # 전체 답안은 하나도 안입은 경우를 제외해서 -1

5. 풀이 2: 답안 확인

Python

6 lines

from collections import Counter
def solution(clothes):
    answer = 1
    for l in list(Counter([j for i, j in clothes]).values()):
        answer = answer * (l+1)
    return answer -1

둘 모두 예시 테스트케이스도 모두 성공했으니 답안을 제출했습니다.

공부할 때에는 이렇게도 해보고 저렇게도 해보는게 필요한 것 같습니다.

제출 답안 분석 및 복잡도 확인

Gemini의 도움을 받아 저의 답안에 대한 평가를 해봅니다.

제출 답안 1 - 시간 복잡도: $O(N \times L) \approx O(N)$

전체 의상 수 $N$ ( $N \le 30$ ), 의상 종류 이름 문자열의 최대 길이 $L$ ( $L \le 20$ ) 기준입니다.
clothes 배열을 단일 루프로 순회하며 딕셔너리에 삽입/갱신하는 연산은 해시 충돌이 없는 평균 $O(N \times L)$ 입니다.
고유 의상 종류 수 $K$ ( $K \le N$ )에 대해 dc.values()를 순회하며 곱셈을 수행하므로 $O(K)$ 가 소요됩니다.
$N \le 30$ 이므로 사실상 수십 번의 연산 내외로 $0.001$ 초 이내에 즉시 통과합니다.

공간 복잡도: $O(K \times L) \approx O(N)$

의상 종류별 등장 횟수를 저장하는 defaultdict에 최대 $K$ 개의 키-값 쌍이 저장됩니다.

제출 답안 총평

장점: defaultdict(int)를 사용하여 KeyError 검사 분기 없이 빈도를 직관적이고 안정적으로 누적했습니다.

제출 답안 2 - 시간 복잡도: $O(N \times L) \approx O(N)$

리스트 컴프리헨션으로 의상 종류 리스트를 추출하는 데 $O(N)$ 이 듭니다.
Counter 객체 생성에 $O(N \times L)$ , .values()의 list 변환에 $O(K)$ , 곱셈 루프에 $O(K)$ 가 듭니다.

공간 복잡도: $O(K \times L) \approx O(N)$

[j for i, j in clothes]로 크기 $N$ 의 새로운 리스트를 생성합니다.
Counter 해시 테이블( $O(K)$ )과 list(...)로 변환된 값 리스트( $O(K)$ )가 메모리를 사용합니다.

제출 답안 총평

장점: Counter를 통해 의상 종류별 개수 카운팅을 단 한 줄로 집계하여 파이써닉한 구성을 갖췄습니다.
아쉬운 점:
1. Counter(...).values()는 그 자체로 순회 가능한(iterable) 딕셔너리 뷰 객체이므로 list(...)로 다시 감쌀 필요가 없습니다 (불필요한 메모리 할당).
2. 언패킹 시 사용하지 않는 i 대신 관례적인 언더스코어(_)를 사용하는 것이 좋습니다.
3. 반복문 변수명 l은 숫자 1과 형태가 비슷하여 가독성을 저해할 수 있으므로 count 등으로 명확히 지정하는 것이 좋습니다.

AI 추천 답안

아래는 Gemini가 작성해 준 내용입니다.

사용 AI 모델: Gemini 3.8 Flash (Extended)

추천 1: Counter + math.prod 활용형 (가장 현대적이고 간결한 풀이)

Python 3.8부터 표준 라이브러리로 제공되는 math.prod를 활용하면 별도의 누적 곱셈 루프 없이 문제를 1~2줄로 해결할 수 있습니다.

Python

9 lines

from collections import Counter
from math import prod

def solution(clothes):
    # 의상 종류(category)별 개수 집계
    counts = Counter(category for _, category in clothes)
    
    # 각 종류별 (개수 + 1)의 모든 곱을 구한 후, 아무것도 입지 않은 경우(1)를 차감
    return prod(count + 1 for count in counts.values()) - 1

동작 원리: 제너레이터 표현식 (category for _, category in clothes)으로 중간 리스트 생성 없이 Counter를 만듭니다. math.prod를 통해 (count + 1) 값들의 총곱을 한 번에 구하고 최종적으로 1을 차감합니다.

추천 2: defaultdict 최적화형 (기본 모듈 기반 정석 풀이)

제출 답안 1의 가독성과 안정성을 유지하면서 다듬은 정석적인 형태입니다.

Python

12 lines

from collections import defaultdict

def solution(clothes):
    clothes_count = defaultdict(int)
    for _, category in clothes:
        clothes_count[category] += 1
        
    answer = 1
    for count in clothes_count.values():
        answer *= (count + 1)
        
    return answer - 1

동작 원리: 사용하지 않는 변수는 _로 명시하고, 누적 곱 연산자 *=를 활용하여 코드의 가독성과 안정성을 높였습니다.

제출 답안 vs AI 추천 답안 비교

5열 × 3행

비교 항목	제출 답안1 (defaultdict)	제출 답안2 (Counter + list)	추천 답안 1 (Counter + math.prod)	추천 답안 2 (defaultdict 정석)
시간 복잡도	$O(N)$	$O(N)$	$O(N)$	$O(N)$
공간 복잡도	$O(K)$	$O(N)$ (중간 리스트 2회 생성)	$O(K)$ (제너레이터 사용)	$O(K)$
메모리 효율	우수	중간 리스트 복제 낭비 있음	매우 우수	우수

두 제출 답안 모두 문제의 핵심 수학적 원리인 $\prod (k_i + 1) - 1$ 을 올바르게 파악하여 시간 및 공간 복잡도 측면에서 효율성 테스트를 가뿐히 통과합니다.다만 실전 코딩테스트 및 코드 리뷰 관점에서는 추천 1처럼 제너레이터와 math.prod를 결합하여 중간 임시 객체 생성을 최소화하고 2줄로 압축하는 방식이 가장 모던한 평가를 받습니다. 만약 내장 라이브러리 사용을 최소화하며 직관성을 살리고자 한다면 추천 2와 같이 미사용 import를 정리하고 _ 언패킹을 적용하는 방식이 적절합니다.

회고

이런 문제를 풀 때면 알고리즘 문제들은 IT 직무의 실력을 판가름 하는 것이 아니라

수학적 능력을 보고자하는 문제라는 생각이 듭니다.

표준 라이브러리 활용 능력은 암기의 영역 같아서 암기를 잘 못하는 저로서는 별로 좋지는 않네요.

다음 문제부터는 다른 유형의 1~2 레벨을 먼저 공부해보겠습니다.

감사합니다.

[프로그래머스] 해시 - 의상

프로그래머스 코딩테스트 고득점 Kit 학습하기 (6편)

의상

문제 설명

제한 사항

입출력 예

입출력 예 설명

나의 풀이

1. 초기화 상태

2. 풀이 1: 풀이 과정

3. 풀이 1: 답안 확인

4. 풀이 2: 풀이 과정

5. 풀이 2: 답안 확인

제출 답안 분석 및 복잡도 확인

AI 추천 답안

추천 1: Counter + math.prod 활용형 (가장 현대적이고 간결한 풀이)

추천 2: defaultdict 최적화형 (기본 모듈 기반 정석 풀이)

제출 답안 vs AI 추천 답안 비교

회고

댓글 (0개)

[프로그래머스] 해시 - 전화번호 목록

마지막 글입니다

카테고리 인기 포스트

Gemini Notebook (구 NotebookLM) 이용하여 제작한 코딩테스트 파이썬 마스터북 공유

Gemini Notebook (구 NotebookLM) 이용하여 프로그래머스 코딩테스트 고득점 Kit 학습하기

[프로그래머스] 해시 - 전화번호 목록