[프로그래머스 해시]위장- Python3

문제

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

코딩테스트 연습 - 위장 | 프로그래머스

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

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

종류                                                                            이름

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

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

 

제한사항

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

 

입력

clothes                                                                        return

[[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개의 조합이 가능합니다.

 

알고리즘

def solution(clothes):
    answer = 1
    # 해쉬 테이블을 사용하기 위해 딕셔너리 선언
    table = dict()

    # clothes의 각 원소들을 읽어서, 옷의 종류가 key이고, 
    # {옷의 종류1 : 종류1 의 출현 빈도, 옷의 종류2: 종류2 의 출현 빈도}
    # 이런 형태의 딕셔너리를 만들것이다. 

    for i in range(len(clothes)):
        # clothes[i][1]은 옷의 종류를 말한다. 
        # 즉, headgear라는 키에 해당하는 value가 있으면 그 값을 1 증가시킨다.
        try:
            table[clothes[i][1]] += 1
        # headgear라는 key가 딕셔너리에 들어와있지 않으면, 새로 추가하고 그 value를 1로 한다.    
        except:
            table[clothes[i][1]] = 1

    # 딕셔너리에서 value들을 뽑아서, 리스트로 만든다.
    values = list(table.values())
    
    # 각 원소들을 1 증가시킨 후, 모두 곱한다.
    for i in range(len(values)):
        values[i] += 1
        answer *= values[i]

    # 1을 빼주고 리턴한다. 
    answer -= 1
    return answer
    
    
clothes = [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"], ["oldbe", "bottom"], ["oltus", "top"]]
print(solution(clothes))

 

설명

1. 입력으로 받은 2차원 배열 clothes를 순회한다. (이번 문제에서는 옷의 이름에 대한 정보를 필요로 하지 않았기 때문에 버린다. 아마 문제가 더 복잡하게 나온다면, list의 형태로 만들어서, 옷의 종류에 해당하는 value값으로 지정해야지 싶다)
2.  clothes[i][1]번째 원소를 key로 만들고, 그 값이 출현할 때마다 그 빈도 값을 1 증가시킬 것이다. 그러나, 어떠한 키값이 처음 들어올 경우 증가시킬 value가 선언되어 있지 않기 때문에, 선언해 주어야 한다. 따라서 try문에서 해당 키값을 1 증가시키는 구문을 실행하고, 이에 오류가 난다면 except문에서 새로운 키값과 value를 초기화해서 선언한다. 
3. 만들어놓은 딕셔너리에서 values()를 통해 값들을 뽑아서, list로 만든다
4. 각 원소들의 값을 1씩 더하고, 모두 곱해준 후 1을 뺀 값을 리턴한다. 이것은 아래의 예를 보면서 살펴보자

 

종류:  이름

A: [a1, a2, a3]

B: [b1, b2]

C: [c1, c2]

 

위의 경우처럼 옷의 종류가 3가지이고, 각 종류에 해당하는 옷들이 있다고 하자. 경우의 수를 구함에 있어서, 제약 사항은 다음과 같다. 

• 한 종류의 옷은 하나만 선택할 수 있다
• '적어도' 한 종류의 옷은 입어야 한다

우리는 좀 더 자세히 경우를 나눠볼 수 있다. A에서 옷을 고르는 경우는 (a1을 고르는 경우, a2를 고르는 경우, a3을 고르는 경우, A에서 옷을 고르지 않는 경우) 이렇게 4가지로 나눠진다. B를 고르는 경우 또한, (b1을 고르는 경우, b2를 고르는 경우, B에서 옷을 고르지 않는 경우)이렇게 3가지로 나뉜다. C도 마찬가지이다. 그리고 모든 경우의 수를 구하려면, A, B,C 에서 구한 경우의 수를 모두 곱해주면 된다. 이를 일반화시켜보면,

모든 경우의 수 = (A의 출현 빈도 + 1) * (B의 출현 빈도 + 1) * (C의 출현 빈도 + 1)

이러한 값을 구하면 된다. 그러나, 3가지 종류의 옷을 아무것도 입지 않는 경우는 제약 사항에 위배되므로, 1을 빼줘야 한다. 

원하는 경우의 수 = (A의 출현 빈도 + 1) * (B의 출현 빈도 + 1) * (C의 출현 빈도 + 1) - (아무것도 입지 않는 경우의수 1)

를 리턴한다. 

 

결과

원하는 결과를 출력한다.

후기

시간 복잡도를 줄이기 위해, 배열을 순회하는 법 보다는 해쉬, 즉 딕셔너리를 이용해서 문제를 해결하는 방법을 공부하던 중 이 문제를 풀게 되었다. 근데 사실 해쉬와는 큰 연관이 없는 문제였다. 효율성 테스트도 없는 문제여서 더더욱 해쉬와는 연관이 없었다. 그래도 해쉬를 사용해서 내가 원하는 형태의 자료구조를 만들었다. 다른 문제에서 배열을 사용하는 방법보다 시간복잡도를 줄일 수 있는 방법으로 활용할 수 있을 것이라 생각한다. 

문제에서 좀 애를 먹었던 부분은, 경우의 수를 구하는 방법이었다. 경우의 수를 구하는 것이 기억이 잘 안나서, 한참을 고민했다, 뭐 for문을 돌면서 컴비네이션을 해가지고 구해야 되나~ 하면서 한참을 뻘짓하다가, 뭔가 좀 쉽게 구할 수 있을 것 같은데 하면서 머리를 엄청 굴리다 보니 위와같은 방법을 떠올리게 되었다.

다른사람의 풀이를 보니, 라이브러리를 이용해서 엄청 간단하게 풀었다. 물론 나는 해쉬 자료구조를 연습하기 위해 일부러 저렇게 풀긴 했는데, 라이브러리도 모르고 안쓰는거랑 알고 안쓰는거랑은 다르니깐 짬짬이 공부해봐야겠따. ^__^