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

ZEDY·2024년 3월 6일

의상 파이썬 프로그래머스 해시

문제

풀이

내가 생각한 알고리즘

Lesson Learn

해시

왜 collections 모듈의 defaultdict를 사용한거야?

[코딩테스트] 알고리즘 문제풀이

목록 보기

3/46

문제

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

풀이

내가 생각한 알고리즘

가능한 모든 조합을 생각하되, 같은 카테고리 안에 두개 이상 나오면 안된다.
종류 별로 해시 저장을 하고, (Key-Value)
Key값이 같은 것의 리스트 원소 중 하나 혹은 0개 반환해 조합을 센다.
-> 조합을 실제 구현하는 것이 아니라, 조합의 개수만 구하면 되는 문제이기 때문에 연산을 해 구하였다.

코드

from collections import defaultdict

def solution(clothes):
    table = defaultdict(list)
    for cloth in clothes:
        table[cloth[1]].append(cloth[0])
        
    answer = 1
    
    for one_row in table.values():
        answer *= (len(one_row) + 1)
    answer -= 1
    return answer

Lesson Learn

해시

해시(Hash)는 임의의 길이의 데이터를 고정된 길이의 값으로 매핑하는 것을 말합니다. 이 고정된 길이의 값은 해시 코드 또는 해시 값이라고도 합니다.

해시 함수는 임의의 데이터를 입력으로 받아 이러한 해시 값을 생성하는 함수입니다. 이러한 함수는 다음과 같은 특성을 가집니다:

고정된 길이의 출력: 해시 함수는 임의의 길이를 가진 입력에 대해 항상 고정된 길이의 출력을 생성합니다. 이는 해시 함수가 입력 데이터의 크기에 관계없이 항상 동일한 길이의 해시 값을 반환한다는 것을 의미합니다.
고유한 매핑: 같은 입력에 대해 항상 같은 해시 값을 생성합니다. 즉, 입력이 같으면 해시 값도 항상 같습니다. 그러나 해시 함수는 다른 입력에 대해서는 가능한 한 서로 다른 해시 값을 생성하려고 합니다.
해시 충돌: 서로 다른 입력에 대해 동일한 해시 값을 생성할 수 있습니다. 이를 해시 충돌이라고 합니다. 해시 충돌은 해시 함수가 서로 다른 입력을 고유한 해시 값으로 완벽하게 매핑하는 것을 보장하지 않기 때문에 발생합니다.

해시 함수는 다양한 분야에서 사용됩니다. 예를 들어, 데이터의 무결성을 검증하거나 데이터를 검색하기 위한 빠른 액세스를 위해 사용됩니다. 해시 테이블은 이러한 해시 함수의 개념을 기반으로하여 구현되어 효율적인 데이터 검색을 제공합니다.

파이썬에서는 해시 함수는 딕셔너리나 셋과 같은 내장 자료 구조의 키로 사용될 때 주로 사용됩니다. 이러한 자료 구조는 해시 테이블을 기반으로 하며, 해시 함수를 사용하여 키와 값을 관리합니다.

딕셔너리

딕셔너리는 파이썬에서 매우 유용한 데이터 구조 중 하나입니다. 딕셔너리는 키(key)와 값(value)의 쌍으로 이루어진 데이터 구조를 말합니다. 각 키는 값에 대응되며, 이를 통해 키를 사용하여 값을 검색할 수 있습니다.

딕셔너리는 중괄호 {}를 사용하여 정의하며, 키와 값은 콜론(:)으로 구분합니다. 예를 들어:

my_dict = {'apple': 2, 'banana': 3, 'orange': 5}

위의 예제에서 'apple', 'banana', 'orange'는 각각 키이고, 2, 3, 5는 각각 해당하는 값입니다.

딕셔너리는 다음과 같은 특징을 가집니다:

키는 고유해야 합니다. 즉, 중복된 키는 허용되지 않습니다. 하나의 딕셔너리에는 같은 키가 두 번 이상 나타날 수 없습니다.
값에는 제한이 없습니다. 딕셔너리의 값은 어떠한 데이터 타입이든 될 수 있습니다.
딕셔너리는 순서가 없는 자료형입니다. 즉, 딕셔너리에 추가된 순서대로 요소에 접근할 수 없습니다.

딕셔너리는 데이터를 효율적으로 검색할 수 있는 빠른 검색 속도를 제공합니다. 키를 사용하여 값을 가져오기 때문에 많은 양의 데이터를 처리할 때 유용합니다. 따라서 딕셔너리는 파이썬에서 매우 자주 사용되는 데이터 구조 중 하나입니다.

왜 collections 모듈의 defaultdict를 사용한거야?

collections 모듈의 defaultdict 클래스는 기본값(default)을 가진 딕셔너리를 생성하는데 사용됩니다. 이 클래스를 사용하면 딕셔너리의 키를 처음으로 만들어질 때 기본값으로 설정할 수 있습니다.

일반적인 딕셔너리에서는 존재하지 않는 키에 접근하려고 하면 KeyError가 발생합니다. 그러나 defaultdict를 사용하면 키가 없을 때 지정된 기본값을 반환하게 됩니다.

defaultdict를 사용하는 이유는 특히 여기서의 예제처럼 리스트, 셋 등과 같은 복합 데이터 구조를 딕셔너리의 값으로 가질 때 유용합니다. 기본적으로 딕셔너리는 키에 대한 값만을 저장할 수 있으므로, 리스트나 셋과 같은 여러 값을 하나의 키에 매핑하려면 기존 딕셔너리로는 번거로운 작업이 필요합니다.

따라서 defaultdict를 사용하면 편리하게 여러 값을 가진 딕셔너리를 초기화할 수 있습니다. 이 예제에서는 각 의상 종류에 해당하는 의상 이름의 리스트를 초기화할 때 사용되었습니다. defaultdict를 사용하면 코드가 간결해지고 편리해집니다.

즉, 초기화 오류가 발생하지 않도록 하기 위함입니다.

규칙을 찾는 것도 어렵지만 수학식을 세우는게 참 어렵다..
중학교 때 공부 더 잘해놓을껄