프로그래머스 - 위장

프로그래머스의 코딩테스트 고득점 Kit의 해시유형 문제들 중 Level 2 ‘위장’을 풀어보았습니다.

프로그래머스 - ‘위장’ 문제 보러 가기 !
https://programmers.co.kr/learn/courses/30/lessons/42578

문제 설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

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

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

제한사항

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

입출력 예

문제 접근 방식

이번 문제는 경우의 수 공식을 구하면 금방 풀 수 있는 문제이지만, 나는 공식을 잘 모르겠어서 시간이 조금 걸렸다.
각 의상의 종류마다 입을 수도 있고 안입을 수도 있기때문에 옷을 입지 않는 경우를 하나 추가한다.
그리고 옷을 고르는 행위는 동시에 일어나므로 곱셈으로 계산한다.
마지막으로 옷을 아예 입지 않는 경우를 고려하여 1을 뺀다.

위의 첫번째 입출력 예시를 예로 들자면, 해쉬로 구현했을 떄 아래와 같은 객체가 만들어진다.
{‘headgear’: 2, ‘eyewear’: 1}
headhear 종류는 2개, eyewear 종류는 1개.
따라서 result = (2+1) * (1+1) -1이다.

풀이 코드

def solution(clothes):
    # dict의 value값을 int 타입으로 초기화
    hash_clothes = defaultdict(int)

    # 같은 종류일 경우 +1
    for a,b in clothes:
        hash_clothes[b] += 1
    answer = 1

    # 경우의 수 : answer *= (옷 가지 수 + 안 입을 경우)
    for i in hash_clothes.values():
        answer *= (i+1)

    # 옷을 아예 안 입는 경우 빼주기
    return answer-1

마무리

획기적으로 빠른 속도의 특징을 갖는 해쉬를 이용

Hash

• Hash Table : 키에 데이터를 저장하는 데이터 구조
  • Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
  • 테이블의 예 : Python의 Dictionary(딕셔너리)타입이 해쉬
  • 파이썬에선 딕셔너리 타입이 있기 때문에 해쉬를 별도 구현할 이유가 없음
• 용어
  • 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것
  • 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
  • 해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터(Value) 위치를 찾을 수 있는 함수
  • Key를 해싱 함수로 연산해서, 해쉬 주소를 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 알 수 있음