# 해시 - 위장

- Author: @mildsalmon
- Published: 2021-12-17
- Updated: 2021-12-17
- Source: http://blex.me/@mildsalmon/%ED%95%B4%EC%8B%9C-%EC%9C%84%EC%9E%A5
- Tags: 파이썬, 알고리즘, 프로그래머스, 코딩테스트, 문제

---

# 1. 위장

- 난이도
	- Level 2
- 출처
	- [코딩테스트 연습 - 위장 | 프로그래머스 (programmers.co.kr)](https://programmers.co.kr/learn/courses/30/lessons/42578)

### A. 📜 문제

위 프로그래머스 사이트에 접속하여 문제를 확인해주세요.

### B. 💡 내 답안

##### a. 😅 1차 시도 (실패)

```python

from itertools import combinations

def solution(clothes):
    clothes_dict = {}
    answer = 0
    kind_len = 0

    for name, kind in clothes:
        if kind in clothes_dict:
            clothes_dict[kind] += 1
        else:
            clothes_dict[kind] = 1
        kind_len += 1

    clothes_len_list = list(clothes_dict.values())

    for i in range(1, kind_len + 1):
        # 조합에서 시간초과가 발생했을 것이다.
        # 만약, 옷의 종류가 30가지라면 $_{30}C_{15}$ (n=30, r=15인 조합)의 경우 155,117,520개가 발생하므로 시간초과가 당연하다.
        for combi in list(combinations(clothes_len_list, i)):
            temp = combi[0]
            for j in range(1, i):
                temp *= combi[j]
            answer += temp

    return answer

```

##### b. 😊 2차 시도 (성공 - 경우의 수)

```python

from itertools import combinations

def solution(clothes):
    clothes_dict = {}
    answer = 1

    for name, kind in clothes:
        if kind in clothes_dict:
            clothes_dict[kind] += 1
        else:
            clothes_dict[kind] = 1
    """
    [[얼굴A],
     [얼굴B],
     [하의A],
     [얼굴A, 하의A],
     [얼굴B, 하의A]]
    
    위 경우는 아래처럼 생각할 수 있다.
    
    [[얼굴A, 하의x],
     [얼굴B, 하의x],
     [얼굴x, 하의A],
     [얼굴A, 하의A],
     [얼굴B, 하의A],
     [얼굴x, 하의x]]
    여기서 하루에 최소 한 개의 의상은 입는다고 했으므로 [얼굴x, 하의x]를 제외해준다.
    """
    for _, value in clothes_dict.items():
        answer *= (value + 1)
    answer -= 1

    return answer

```

##### c. 😊 3차 시도 (다른 사람의 풀이)

```python

from collections import Counter
from functools import reduce

def solution(clothes):
    temp = Counter([kind for name, kind in clothes])
    answer = reduce(lambda x, y: x * (y + 1), temp.values(), 1) - 1

    return answer

```

##### a. 🙄 회고

> 내 풀이

- 처음에는 단순 조합으로 시도했다.
	- 최악의 경우를 상상하지 못하여 시간초과가 발생했다.

### C. 🧐 문제 해설

> 이해한 내용을 바탕으로 작성했습니다.

- 최악의 경우도 잘 생각해보자.
	- 순열은 11!가 4000만 정도이다. 따라서 n이 10인 경우가 마지노선이다.
	- 조합은 \[n=28, r=14\]인 경우가 4000만 정도이다. \[n=26, r=13\]인 경우는 1000만 정도이다. 따라서 최악의 경우 n이 26을 넘기면 안된다.
		- 이번 문제에서는 n이 26이라고 가정한다면, r이 1~26인 모든 경우를 탐색해야하므로 n이 더 낮아져야한다.

이 외의 내용은 코드에 주석으로 다 남겨놨다.

# 참고문헌

위클리 챌린지. [코딩테스트 연습 - 위장 | 프로그래머스 (programmers.co.kr)](https://programmers.co.kr/learn/courses/30/lessons/42578). Programmers. (accessed Dec 17, 2021)