[프로그래머스] 위장 (해시 Lv. 2) - 파이썬 Python

0. 동일 유형 문제

• [프로그래머스] 완주하지 못한 선수 (해시 Lv. 1)
• [프로그래머스] 전화번호 목록 (해시 Lv. 2)
• [프로그래머스] 위장 (해시 Lv. 2)
• [프로그래머스] 베스트 앨범 (해시 Lv. 3)  

  

 

1. 문제 설명 (출처 : 프로그래머스, 원 출처)

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

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

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

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

제한사항

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

입출력 예

clothes	return
[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crowmask", "face"], ["bluesunglasses", "face"], ["smoky_makeup", "face"]]	3

입출력 예 설명

• 예제 #1 : headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.
  1. yellow_hat
  2. blue_sunglasses
  3. green_turban
  4. yellow_hat + blue_sunglasses
  5. green_turban + blue_sunglasses
• 예제 #2 : face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.
  1. crow_mask
  2. blue_sunglasses
  3. smoky_makeup

 

 

2. 문제 접근 방식 (문제 단순화 하기)

• 늘 그렇듯, 문제를 간단하게 만들어보는 것이 1단계이다.
• 여러 종류의 옷이 있고 각 종류별로 1개 이하를 입을 수 있다면 몇 가지의 옷이 가능하냐는 문제이다.
• 약간 이상하긴 하지만, 위 예제에 따르면 yellow_hat만 입은 것도 옷을 입은 것으로 친다고 하는 것을 보아, 여러 종류 중 하나만이라도 입은 상태도 포함하여 모든 경우의 수를 계산하는 문제이다.
• 위의 예제 #1을 단순화하면 아래와 같은 그림이 나온다.

• headgear는 총 2개 있으니, 스파이에게는 총 3가지의 경우의 수가 있다.
  1. 1번을 입는다.
  2. 2번을 입는다.
  3. headgear를 아무것도 입지 않는다.
• eyewear는 총 1개 있으니, 스파이에게는 총 2가지의 경우의 수가 있다.
  1. 1번을 입는다.
  2. eyewear를 입지 않는다.
• 그렇다면 총 3 x 2 가지의 경우의 수 인 6가지가 존재하고, 이 중 한 가지는 headgear도 입지 않고 eyewear도 입지 않은 경우가 되기 때문에 이 경우를 제외하 5가지가 정답이 되게 된다.
• 이를 컴퓨터 프로그램으로 짜서 컴퓨터에게 일을 시키기 위한 방법은 두 가지가 떠오른다.

 

1. 해결책 1 : 해시를 통해 각 type 별로 가짓수를 계산하고, 총 경우의 수를 산출한다.
2. 해결책 2 : Counter를 활용해서 위의 동작을 조금 더 쉽게 작성해본다

 

 

 

 

 

 

 

 

 

3-1. Hash를 사용한 solution

• 완주하지 못한 선수라는 문제를 풀었다면, 이 문제를 풀기 비교적 쉬웠을 것이다.
• 유사한 유형의 문제를 아래에 첨부하니 아직 풀어보지 않았다면 이 문제에 대한 해답을 보고 나서 풀어보는 것도 큰 도움이 될 것이라 생각한다.
• 2021.09.21 - [네카라쿠배 취준반 - 프로그래머스 문제 풀이] - [프로그래머스] 완주하지 못한 선수 문제 풀이(해시 Lv. 1) - 파이썬 Python

[프로그래머스] 완주하지 못한 선수 문제 풀이(해시 Lv. 1) - 파이썬 Python

def solution(clothes):
    # 1. 옷을 종류별로 구분하기
    hash_map = {}
    for clothe, type in clothes:
        hash_map[type] = hash_map.get(type, 0) + 1
        
    # 2. 입지 않는 경우를 추가하여 모든 조합 계산하기
    answer = 1
    for type in hash_map:   
        answer *= (hash_map[type] + 1)
    
    # 3. 아무종류의 옷도 입지 않는 경우 제외하기
    return answer - 1

print(solution([["crowmask", "face"], ["bluesunglasses", "face"], ["smoky_makeup", "face"]]))

1) HashMap 만들기

• HashMap이란 Key-Value의 Pair를 관리하는 Dictionary이다.
• 이 문제에서 Key는 옷의 종류가 되고, Value는 해당 옷 종류의 가짓수(count)를 의미한다.

2) clothes 배열에 존재하는 모든 옷의 종류의 count table 만들기

• 'Hashing을 한다'라고도 표현하는데, HashMap에 의상 종류를 전부 추가해보자. 
• 위 코드의 동작 방식은 다음 예시로 설명하는 것이 가장 쉽게 이해가 가능할 것이다.

• Hash Map을 보고 나면 별게 아니다. 이 문제에서는 Key 값으로 전화번호를 관리하는 전화번호부 같은 것이다.
• HashMap.get(type, 0)
  • 이 함수는 'B'라는 Key에 해당하는 Value가 있으면 가져오고, 아닐 경우 0을 Default로 지정하여 사용하겠다는 의미의 함수이다.
  • Value는 곧 옷 종류의 가짓수가 되기 때문에, 이전에 값이 있었으면 기존 값에 + 1을 하면 되고
  • 없었으면 1을 입력하면 된다.

3) 각 옷 종류별 경우의 수를 answer에 곱해준다

• 이제 모든 옷 종류의 count가 잘 입력되었다면, answer에 곱해주면 된다.
• 하지만 모든 옷 종류에 대해서 안 입는 경우가 있기 때문에 ans *= it.next().intValue()라고 하지 않고
• ans *= it.next().intValue() + 1을 곱해줘야 한다.
• 즉, +1은 각 옷 종류를 입지 않는 경우를 고려하기 위해 추가되어야 하는 것이다.

4) 예외처리

• 아무리 스파이가 모자 하나만 달랑 입어도 된다고 해도, 아무것도 입지 않는 것은 허용되지 않는 것이 문제의 전제이다.
• 그렇기 때문에 마지막에 -1을 해줘서 모든 옷의 종류를 입지 않은 경우 1개를 제외시켜 주고,
• 예제 #2에서도 동일하게 잘 동작하는 걸 확인하면 제출해보고 정답임을 확인할 수 있다.

3-2. Counter를 사용한 solution

from collections import Counter
from functools import reduce

def solution(clothes):
    # 1. 의상 종류별 Counter를 만든다.
    counter = Counter([type for clothe, type in clothes])

    # 2. 모든 종류의 count + 1을 누적하여 곱해준다
    answer = reduce(lambda acc, cur: acc*(cur+1), counter.values(), 1) - 1
    return answer

print(solution([["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]))

1) Counter 객체로 종류별 count 계산하기

• Counter에 type들만 전달해주면, 아래와 같은 결과가 나온다.

2) 나머지는 Hash Solution과 동일한 동작을 한다.

• 이후로는 위와 완전히 동일한 동작을 하기 때문에 설명을 생략한다.

 

4. 참 쉽죠?

• Hash를 사용해서 문제를 풀 수 있는 방식은 무궁무진하다. 필자도 다른 방식을 먼저 생각해서 풀었는데, 어찌 됐든 정확한 해답을 얻는 빠른 코드라면 전부 좋다.
• 프로그래머스 플랫폼이 정말 좋은 이유는 타 플랫폼 대비 서로의 코드를 보고 배우기 매우 용이하게 되어있다는 점이다. 다른 사람의 코드를 무단 복사나 도용하는 것은 틀린 행위지만, 잘 짜여진 코드를 보는 것만큼 좋은 공부법도 없어 보인다.
• 잘 짜여진 코드는 직관적이고 읽기도 편해서, 이런 코드는 보다 보면 이 사람이 어떤 생각으로 문제를 접근했는지 까지도 보이게 된다. 꼭 문제를 본인만의 방식으로 해결한 뒤에 더 뛰어난 사람들의 코드를 보면서 배우는 시간을 가지면 좋을 것 같다.

 

5. 동일 유형 문제

• [프로그래머스] 완주하지 못한 선수 (해시 Lv. 1)
• [프로그래머스] 전화번호 목록 (해시 Lv. 2)
• [프로그래머스] 위장 (해시 Lv. 2)
• [프로그래머스] 베스트 앨범 (해시 Lv. 3)