[Programmers] 위장 (Lv.2)

프로그래머스에 '위장' 문제는 코딩테스트 고득점 Kit에 해시 카테고리에 있다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

 

📚 해시 알고리즘이란?

https://amazelimi.tistory.com/30?category=990184 

[Python] 해시(Hash)란 무엇인가(feat. Dictionary 자료구조) | LIM

 

🧐 내가 생각한 문제 해결 순서

1. 해시 알고리즘을 이용하셔 Python Dict 로 종류와 해당 의상 매칭

{
  'headgear': ['yellow_hat', 'green_turban'], 
  'eyewear': ['blue_sunglasses'],
  'face': ['crow_mask']
 }

 

2. 종류의 조합을 구해서 가지고 있는 의상 개수만큼 곱하기

ex) ('headgear', 'eyewear'): 2 * 1 = 2

      ('headgear', 'face'): 2 * 1 = 2

      ('eyewear', 'face'): 1 * 1 = 1

      ('headgear', 'eyewear', 'face'): 2* 1* 1 = 2

>> 2 + 2 + 1 + 2 + 4(한개씩만 입는다고 가정) = 11개

 

 

위와 같이 구현했을 때 

from itertools import combinations

def solution(clothes):
    answer = 0
    combis = []
    clothes_kind = {}
    for clothe in clothes:
        if clothes_kind.get(clothe[1]) == None:
            clothes_kind[clothe[1]] = 0
        clothes_kind[clothe[1]]+=1

    kinds = list(clothes_kind.keys())
    for i in range(1, len(kinds)+1):
        combis.extend(list(combinations(kinds, i)))
    
    for combi in combis:
        cobmi_count = 1
        for kind in combi:
            cobmi_count *= clothes_kind[kind]
        answer += cobmi_count
    return answer

1번에서 시간초과가 나오고, 다른 예제에서도 시간이 오래걸리는 걸 볼 수 있다.(Test4, Test7, Test26)

 

그럼 어떻게 해야할까 고민을 1시간 정도 하다가 답이 안나와서 찾아봤다..

 

역시..다른 방법이 존재했다.

---

아이디어는 간단하다..내가 생각을 못했을뿐..!

📌 스파이가 옷을 입는 경우, 입지 않는 경우 2가지로 제한하기

문제에서 스파이는 종류별로 1개씩만 입으면 되고 몇개를 입을지는 제한이 없었다. 따라서 스파이가 어떤 종류를 입을때, 입지 않을때 두가지 경우만 생각하면 됐다!

 

예를 들어서, 동일하게 아래 예제에서 스파이가 headgear에서 선택하는 방법은 다음과 같다.

1. 'yellow_hat'

2. 'green_turban'

3. headgear를 입지 않는경우

>> 총 3가지이다.

 

따라서 종류별로 모든 경우의 수는 그 종류의 (옷가지수 + 1) 이다.

+1 은 아예 그 종류를 입지 않을때 경우의 수이다.

{
  'headgear': ['yellow_hat', 'green_turban'], 
  'eyewear': ['blue_sunglasses'],
  'face': ['crow_mask']
 }

 

그렇다면 경우의 수는 다음과 같이 정의될 수 있다.

headgear: 3

eyewear: 2

face: 2

>> 3* 2* 2 = 12

 

하지만 위 예제의 정답은 11이다. 

 

그 이유는 스파이가 옷을 아예 입지 않는 경우는 없다고 했기 때문에 마지막에 1을 빼주어야 한다.

 

따라서 최종 정답은 12-1=11 이 되게 된다!

 

위 로직을 반영한 코드는 이렇다.

def solution(clothes):
    answer = 1
    clothes_kind = {}
    for clothe in clothes:
        if clothes_kind.get(clothe[1]) == None:
            clothes_kind[clothe[1]] = 0
        clothes_kind[clothe[1]]+=1

    for kind, count in clothes_kind.items():
        answer *= (count+1)
        
    return answer - 1

 

 

다 맞은 것도 다 맞은 건데 속도가 무지 빠르다..

 

🙂 느낀점

알고리즘 문제 풀때 최대한 조합은 자제하도록 하자..시간 복잡도가 너무 올라간다..