프로그래머스 의상 파이썬(python)

시작하며

프로그래머스 고득점 kit 카테고리 중 해시에 관련된 문제이므로

1. 해시맵 설명
2. 첫번째 코드 / 해설
3. 두번째 코드 / 해설
   이렇게 글을 작성하겠습니다.

해시맵이란?

• 키를 값에 mapping하는 데이터 구조
• 키의 hash()를 사용하여 내부의 해시 테이블에 데이터를 저장
• 파이썬에서는 dict 타입을 통해서 일반적으로 구현
• 평균적으로 상수 O(1) 시간 내에 연산을 해서 매우 효율적
• 하지만 시간 복잡도는 O(n)

자주 사용되는 해시맵의 메서드들

• dict[key]: 키에 해당하는 값을 반환
  키가 딕셔너리에 없는 경우 KeyError 예외를 발생

• update(): 다른 딕셔너리의 키-값 쌍을 현재 딕셔너리에 추가
  이미 존재하는 키의 경우, 값을 업데이트

    dictionary.update(another_dictionary)

• keys(): 딕셔너리의 키들을 반환하는 뷰(view)를 제공
  이 뷰는 딕셔너리의 키들을 반복(iteration)하기 위해 사용 가능

• values(): 딕셔너리의 값들을 반환하는 뷰를 제공
  이를 통해 딕셔너리의 모든 값들을 반복

• items(): 딕셔너리의 키-값 쌍을 튜플로 묶은 뷰를 반환
  이는 딕셔너리를 순회할 때 자주 사용

    pythonCopy code
    for key, value in dictionary.items():
        print(key, value)

• pop(key): 주어진 키에 해당하는 항목을 dict에서 제거하고, 그 값을 반환
  키가 딕셔너리에 없는 경우 KeyError를 발생

    pythonCopy code
    value = dictionary.pop(key)

• popitem(): 딕셔너리에서 임의의 키-값 쌍을 제거하고 해당 쌍을 튜플로 반환
  Python 3.7 이상에서는 마지막에 추가된 항목을 반환합니다.

1번째 코드 / get메서드 이용

def solution(clothes):
    dic= {}
    for c, t in clothes:
        dic[t] = dic.get(t,0) + 1
    answer = 1
    for i in dic:
        answer *= (dic[i] + 1)
    return answer -1

1. 옷 종류별 개수 계산

for c, t in clothes: 루프를 사용해서 clothes 리스트를 순회하며 각 옷의 종류 별로 개수를 세서 dic에 저장
dic[t] = dic.get(t,0) + 1에서 t(type)이 dic에 존재하면 1을 증가해서 저장하고, 없으면 default값(0)으로 저장한다는 의미

2. 조합의 수 계산
   각 옷 종류별 옷을 입지 않은 경우를 포함하여 조합의 수를 계산

answer *= (dic[i] + 1)에서 +1이 해당 옷 종류를 아예 입지 않은 경우를 추가하기 위함이다.

3. 아무것도 입지 않은 경우 제외

return answer -1에서 모든 옷을 입지 않은 경우를 -1 해준다.

예시

headgear 옷 2벌, eyewear 옷 1벌이 있는 상황
headgear1, headgear2, 안 입기 -> 총 3가지 선택지
eyewear1, 안 입기 -> 총 2가지 선택지
결론적으로 3 * 2 - 1(아무것도 안 입은 경우) = 5가지

2번째 코드 / Counter 이용

def solution(clothes):
    from collections import Counter
    from functools import reduce
    cnt = Counter([kind for name, kind in clothes])
    answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
    return answer

1. Counter 사용:

    pythonCopy code
    cnt = Counter([kind for name, kind in clothes])

   • 이 코드는 리스트 컴프리헨션을 사용하여 clothes 리스트에서 각 옷의 종류(kind)만 추출
   • Counter 객체는 이러한 옷 종류들의 각각의 빈도수를 계산하여, 각 옷 종류별 개수를 담은 Counter 객체를 생성
     예를 들어, clothes가 [["hat", "headgear"], ["sunglasses", "eyewear"], ["turban", "headgear"]]라면

   • cnt는 Counter({'headgear': 2, 'eyewear': 1})

   2. reduce 사용:

      pythonCopy code
      answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1

   • reduce 함수는 주어진 함수를 시퀀스(cnt.values())의 항목에 누적적으로 적용하여 단일 값으로 줄임
     여기서는 lambda x, y: x*(y+1) 함수를 사용
   • cnt.values()는 Counter 객체에서 각 옷 종류별 개수를 반환
     이 예제에서는 [2, 1]을 반환합니다.
   • lambda 함수는 누적값 x와 현재값 y를 인자로 받아,
     각 옷 종류별로 "안 입는 경우"를 포함하여 (y+1)을 곱한 다음,
     최종적으로 모든 옷 종류에 대한 조합의 수를 계산
   • reduce의 세 번째 인자인 1은 초기값으로, 옷을 하나도 입지 않은 경우를 의미
     이 경우는 마지막에 1을 통해 제외합니다.
   • 예를 들어, [2, 1]에 대해 계산하면, (1*(2+1))*(1+1) - 1 = 5입니다.
     이는 가능한 모든 옷의 조합 수에서 아무것도 입지 않은 경우를 뺀 값

reduce 메서드

from functools import reduce

result = reduce(function, sequence[, initial])

• function: 두 인자를 받는 함수
  첫 번째 인자는 누적 값(현재까지의 결과)
  두 번째 인자는 시퀀스에서 현재 처리 중인 요소
  이 함수의 반환 값은 다음 단계의 누적 값
• sequence: reduce에 적용할 iterable(리스트, 튜플 등)
• initial (선택적): 누적 작업의 초기값
  이 값이 제공되면, 시퀀스의 첫 번째 요소 전에 이 값이 위치한 것으로 간주
  제공되지 않으면, 시퀀스의 첫 번째 요소가 초기값으로 사용

reduce 사용 예시

pythonCopy code
from functools import reduce

# 두 숫자를 더하는 함수
def add(x, y):
    return x + y

# 시퀀스 정의
numbers = [1, 2, 3, 4]

# reduce 함수 사용
result = reduce(add, numbers)

print(result)  # 출력: 10

이 예시에서 reduce 함수는 add 함수를 numbers 리스트의 요소들에 누적적으로 적용

1. 처음 두 요소 1과 2에 add 함수 적용: 결과는 3
2. 이전 단계의 결과 3과 다음 요소 3에 add 함수 적용: 결과는 6
3. 이전 단계의 결과 6과 마지막 요소 4에 add 함수 적용: 최종 결과는 10

배운점

• 해시맵의 개념과 자주 사용하는 메서드에 대해서 배웠습니다.
• get 메서드를 사용할 때 초기값을 설정하는 법을 배웠습니다.
• Counter를 사용해 dict를 생성하는 법을 배웠습니다.
• reduce 메서드를 이용하면 누적값을 이용하는 경우 코드를 현저히 줄일 수 있다는 것을 알았습니다.

FAQ

해시맵이 알고리즘 문제 해결에 어떻게 도움이 되나요?

해시맵은 키-값 쌍을 효율적으로 저장하고 검색할 수 있는 데이터 구조로,
다양한 알고리즘 문제를 해결하는 데 있어 핵심적인 역할을 합니다.
해시맵의 장점은 아래와 같습니다.

빠른 검색 시간: 평균적으로 O(1)의 시간 복잡도로 데이터를 검색할 수 있어, 대량의 데이터를 다루는 문제에서 시간 효율성을 크게 개선할 수 있습니다.

동적 데이터 저장: 해시맵은 동적으로 데이터를 추가, 수정, 삭제할 수 있어, 문제의 요구에 따라 유연하게 데이터를 관리할 수 있습니다.

키에 의한 직접 접근: 키를 사용해 직접 값을 접근할 수 있어, 배열이나 리스트에서 요소를 찾기 위해 순차적으로 탐색하는 것보다 훨씬 빠릅니다.

프로그래밍 문제를 해결할 때 dict와 Counter 중 어느 것을 선택해야 하나요?

dict와 Counter는 파이썬에서 제공하는 두 가지 유용한 데이터 구조입니다. 각각의 선택은 문제의 특성과 요구 사항에 따라 달라집니다.

dict의 경우: dict는 키-값 쌍을 저장하는 범용적인 자료 구조로, 유연성이 뛰어나고 사용자 정의 객체를 키로 사용할 수 있습니다. 복잡한 데이터 구조를 구성하거나, 키와 관련된 값이 동적으로 변화하는 경우 dict를 사용하는 것이 좋습니다.

Counter의 경우: Counter는 collections 모듈의 일부로, 요소의 등장 횟수를 카운트하는 데 특화된 dict 서브클래스입니다. 주로 요소의 빈도수를 쉽게 계산하고자 할 때 사용됩니다.
예를 들어, 문자열이나 리스트에서 각 요소의 출현 횟수를 세어야 하는 경우 Counter가 매우 효율적입니다.

reduce 함수는 파이썬에서 어떤 경우에 유용하게 사용되나요?

reduce 함수는 functools 모듈에 속해 있으며, 주어진 함수를 시퀀스의 모든 요소에 누적적으로 적용하여 하나의 값으로 축소합니다.

reduce는 다음과 같은 경우에 유용합니다

집계 작업: 여러 값들을 하나의 결과값으로 집계해야 할 때
예를 들어 합계, 곱셈 등의 연산을 전체 리스트에 적용해야 하는 경우.

함수형 프로그래밍 패턴: 람다 함수와 함께 사용하여 코드를 간결하게 만들고자 할 때

파이프라인 작업: 여러 처리 단계를 거쳐 최종 결과를 도출해야 하는 경우, 각 단계의 결과를 다음 단계의 입력으로 전달하는 방식으로 reduce를 사용할 수 있습니다.