[코테] 99클럽 코테 스터디 2일차 TIL - 해시

 

Question1 - [미들러] 의상

 

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/42578

 

코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.

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

종류이름

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

코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.코니는 하루에 최소 한 개의 의상은 입습니다.코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

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

입출력 예

clothesreturn

[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crow_mask", "face"], ["blue_sunglasses", "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

---

문제풀이 

 

trial1  

 

첫번째 시도했던 내용.

우선 문제를 풀기 위해서 의상 종류(type)별, 아이템별 조합의 개수가 중요하다는 생각에,

해시를 만들어서 각 옷 타입별 아이템의 개수가 몇인지를 key - value로 담았다. 

그리고 옷 타입의 개수를 활용해서 반복문을 돌면서 itertool의 콤비네이션을 활용, 옷 타입의 조합을 생성하고, 

각 타입의 아이템 개수를 곱하는 식으로 전체 조합의 수를 구함. 

 

정확성 모두 통과했지만, 1개 테스트가 시간 초과되었다. 시간 복잡도를 고려 못하고 푼 케이스이다.

1) 우선 itertool로 콤비네이션을 만드는 과정에서 가능한 모든 조합을 생성하기 위해 2^N만큼의 조합 수가 생성된다 (선택 여부) 

2) 각 조합에 대해서 해당 의상 아이템의 종류를 곱하는 연산이므로 총 O(2^N*N) 만큼의 시간 복잡도로

시간이 오래걸리는 듯 해서 다시 풀어야 했음. 

import itertools

def solution(clothes):
    # 해시 만들기 : 옷 종류 : 리스트로 의상 종류 
    clothes_hash = {}
    for lst in clothes: 
        [_, b] = lst  # 옷의 종류를 b로 받음
        if b in clothes_hash: 
            clothes_hash[b] += 1
        else: 
            clothes_hash[b] = 1
    
    num_type = len(clothes_hash)  # 전체 종류 

    count = 0
    for i in range(num_type): 
        result = itertools.combinations(clothes_hash.keys(), i + 1)  # 의상 종류의 조합 생성
        for comb in result:
            temp_count = 1
            for key in comb:
                temp_count *= clothes_hash[key]  # 각 의상 종류마다의 수를 곱함
            count += temp_count
    
    return count

 

trial2 ★

 

의상의 조합을 더 간단하고 빠른 방법으로 구하면서 아이템 수를 곱하는 방법은 없을까? 

의상 종류들의 모든 조합을 구하고 나서, 조합마다 의상 아이템 수를 곱하는 부분을 단축시키려면, 

조합마다 아이템을 구하지 말고 전체 아이템 수에서 모든 조합을 고려하도록 해주면 된다.

 

전체 의상 타입에서 조합할때, 그 타입을 입거나 입지 않거나의 경우의 수도 포함***시켜야 한다. 

만약 모든 존재하는 의상 타입을 입어야 한다는 조건이 있었다면, 전체 count개수는 해시의 모든 value값들을 서로 곱한 결과일 것.

그러나 '입지 않는 경우'를 하나의 옵션으로 추가한다면, 의상 타입마다 (item 수 + 1)의 값을 서로 모두 곱해주고 나서 -1을 해주면 된다 (모든 타입을 안입는 경우 제외) 

 

아래와 같이 전체 아이템 수에서 적절히 조합한다면 훨씬 간단하게 코드가 끝난다. 시간 복잡도는 의상을 종류별 개수 세는 것에서 끝나므로 O(N) 일 것이다. 테스트 통과.!

def solution(clothes):
    clothes_hash = {}  # 의상 종류별 개수를 저장할 딕셔너리 생성
    for _, category in clothes:
        if category in clothes_hash:
            clothes_hash[category] += 1
        else:
            clothes_hash[category] = 1
    
    num_combinations = 1
    for count in clothes_hash.values():
        num_combinations *= (count + 1)  # 각 의상 종류별 개수에 1을 더한 값을 모두 곱함 (선택 안 함 포함)
    
    # 모두 선택하지 않는 경우를 제외하기 위해 1을 빼줌
    return num_combinations - 1

 

---

Question2 - [챌린저] 비슷한 단어

 

문제설명  https://www.acmicpc.net/problem/2179