[프로그래머스] 위장 (Python) / 해시

문제

코딩테스트 연습 - 위장

풀이

이 문제는 알고리즘 스터디에서 설원언니가 풀이해준 문제인데, 복습하면 좋을 것 같아 다시 풀어보며 공부한 후, 정리했다.

from collections import Counter
from functools import reduce

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

• 먼저 서로 다른 의상의 조합의 수를 구하는 공식

  clothes가 [[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgear]] 일 때로 예시를 들어보자.
  여기서 headgear는 yellow_hat(노란모자) , green_turban(초록 터번) 총 2개이고 eyewear는 blue_sunglasses(파란 선글라스) 총 1개 이다.

  이때 종류가 겹치지 않게 입을 수 있는 의상 조합의 수는

  • 노란모자
  • 초록 터번
  • 파란 선글라스
  • 노란 모자 + 파란 선글라스
  • 초록 터번 + 파란 선글라스

  총 다섯 가지다 조합의 수는 아래와 같은 공식으로 구해질 수 있다. 

  (headgear에 해당하는 의상 수 +1) * (eyewear에 해당하는 의상 수 +1) -1

   

  종류 마다 +1 을 하는 경우는 착용하지 않는 경우도 해당해야하기 때문이고, 마지막에 -1 을 하는 이유는 모든 의상을 착용하지 않는 경우는 빼야하기 때문이다.
  이제 이 식을 구현하기 위해 Counter와 reduce를 사용해보자 (아래 새로 배운 내용에 약간의 설명이 적혀있다.)

• Counter를 이용해 category(종류)에 해당하는 옷의 갯수를 딕셔너리 형태로 count에 담는다.

  • 예를 들어 clothes가 [[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgear]] 일 때, 아래와 같이 count가 출력된다.

count = Counter([category for name, category in clothes])
print(count)

# 	Counter({'headgear': 2, 'eyewear': 1})

• 아래 공식을 reduce로 나타내보자.

  (headgear에 해당하는 의상 수 +1) * (eyewear에 해당하는 의상 수 +1) - 1

  아래와 같이 나타낼 수 있다.

  reduce(lambda x, y : x * (y+1), count.value(), 1) -1

  • 3번째 인자에 1을 주어 x 를 1로 초기화한다(initializer).

  • 2번째 인자는 category에 해당하는 의상의 수가 차례대로 y에 담기도록 한다.

  • count가 Counter({'headgear': 2, 'eyewear': 1}) 일 때로 예시를 들어보면 reduce를 실행하면 아래 식이 계산된다.

     

    1((1 * (2+1)) * (1+1)) -1 # 5
    따라서 조합의 수 5가 정답으로 return 된다.

     

   

새로 배운 내용

• Counter

  사용 방법

  from collections import Counter

  • 이는 같은 값의 갯수를 딕셔너리 형태로 나타낸다.

  • 사용 예시

list = ['a', 'a', 'b', 'c', 'c']
print(collections.Counter(list))

• 위와 같은 list를 Counter에 넣고 print 하면 아래와 같이 출력 된다.
  

   

   

   

Counter({'a': 2, 'c': 2, 'b': 1})

이때 value(갯수) 기준 내림차순으로 담겨져있음을 알 수 있다.

• reduce

  사용 방법

  from fucntools import reduce

  • 이는 특정 식을 수행할 수 있게 도와준다.

  • 기본 사용 방식은 아래와 같다

     

from fucntools import reduce

• 사용 예시

nswer = reduce(lambda x, y : x + y, [1,2,3,4,5])
# ((((1 + 2) + 3) + 4) + 5)
print answer
# 15

최초 발행 날짜: 2020-12-21