해시 - 위장

1. 위장

• 난이도
  • Level 2
• 출처
  • 코딩테스트 연습 - 위장 | 프로그래머스 (programmers.co.kr)

A. 📜 문제

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

B. 💡 내 답안

a. 😅 1차 시도 (실패)

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차 시도 (성공 - 경우의 수)

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차 시도 (다른 사람의 풀이)

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). Programmers. (accessed Dec 17, 2021)