[python] 프로그래머스 - 위장

 

출처 : 프로그래머스 코딩테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/42578

코딩테스트 연습 - 위장

 

왜 옷을 다 안 입니. 바바리맨도 아니고.

정말 단순한 생각이 문제 풀이의 실마리.

 

 

첫 번째 풀이 : 테스트 케이스1 시간 초과

 

from itertools import combinations

def solution(clothes):
    closet = {}
    answer = 0
    
    for cloth in clothes:
        if cloth[1] not in closet:
            closet[cloth[1]] = 1
        else:
            closet[cloth[1]] += 1
    
    for category in range(len(closet)):
        wear = combinations(closet.values(), category + 1)
        
        for cloth in wear:
            multiple = 1
            for num in cloth:
                multiple *= num
            answer += multiple
        
    return answer

 

일단 문제를 보자마자 처음 든 생각은

 

• 물건 종류별로 사전 자료형으로 만들어서 개수 계산하면 쉽겠다.
• 조합 쓰는 것 같다.

라는 생각이 들었다. 만약 3가지 종류의 옷이 각각 1개, 2개, 3개가 있다면

정답은 1 + 2 + 3 + (1*2) + (1*3) + (1*2*3) = 17이 되므로

이를 어떻게 계산할까 고민하다가 조합을 사용해서 1개, 2개, 3개씩 뽑는 조합을 사용하여

각 조합 안에 있는 항목들을 모두 곱한 것을 전체에 곱하는 즉, 식과 동일하게 계산하는 방법으로 코드를 짰다.

 

하지만 효율성 테스트는 없지만 정확도 테스트에서(조차) 시간 초과가 떴다.(노답 풀이)

 

 

두 번째 풀이 : 질문하기 슬쩍 보고 품

 

def solution(clothes):
    closet = {}
    
    for cloth in clothes:
        if cloth[1] not in closet:
            closet[cloth[1]] = 1
        else:
            closet[cloth[1]] += 1
            
    answer = 1
    
    for num in list(closet.values()):
        answer *= (num + 1)
        
    return answer - 1

 

첫 번째 풀이를 풀고 itertools 라이브러리가 모든 코딩 테스트에서 사용이 가능할까?라는 생각이 들어서

검색해봤더니 역시나... 삼성 21년 상반기 코테 기준으로 사용이 불가능하다는 게시글들이 보였다.

그래서 itertools 라이브러리를 제거하고 식대로 푸는 방법을 생각해보았는데

 1 + 2 + 3 + (1*2) + (1*3) + (1*2*3) 형태로 식을 구현하는 방법이 마땅하지 않았다.

그 때 깨달았어야 했는데, 이 식대로 풀면 틀린거더라.

 

정답은 정말 간단한 경우의 수인데 옷의 종류에 '입지 않음'을 추가하고 이를 전부 곱한 후

문제의 조건에 따라 모두 다 입지 않는 경우의 수 1개를 빼는 것이 답이다.

질문하기 슬쩍 볼 때 하나를 빼라길래 뭐지했는데 깨닫고 자괴감이 넘쳐올랐다.

 

 

세 번째 풀이

 

def solution(clothes):
    closet = {}
    
    for cloth in clothes:
        if cloth[1] not in closet:
            closet[cloth[1]] = 1
        else:
            closet[cloth[1]] += 1
            
    answer = 1
    
    for num in closet.values():
        answer *= (num + 1)
        
    return answer - 1

 

곰곰히 보다가 closet.values()를 굳이 list로 다시 만들 필요가 있나? 싶더라.

list화 하는 것도 O(N)만큼 시간이 들지않나? 싶어서 없애봤더니 없어도 잘 된다.

나 같은 경우 list로 만드는 건 print해서 보기 편하라고 쓰는 경우가 많아서...

closet.values() 말고 closet에서

 

for category, num in closet:

 

과 같이 구현할 수도 있겠다.

 

---

시간 복잡도

 

첫 번째 풀이의 시간 복잡도는

 

사전 자료형으로 만드는 for문 : O(N)

category for문 : 가지수가 최대 30개로 제한되기 때문에 A(상수) * 내부 로직 복잡도

category for문 안의 combination 연산자의 복잡도 : O(N^min{k, N-k}) (참고)

wear for문의 복잡도 : O(nCk)

 

사실 계산이 정확한지는 잘 모르겠는데 짧은 지식으로 봐도

combinations 메소드가 N이나 k가 커질수록 시간 복잡도가 급격히 증가하므로

이를 몇 번이나 반복하는 첫 번째 풀이는 굉장히 오래 걸린다.

 

세 번째 풀이의 시간 복잡도는

 

사전 자료형으로 만드는 for문 : O(N)

closet.values() for문 : O(N)

 

으로 O(N)이다.

 

 

다른 사람의 풀이를 보면서 알게 된 점

 

Counter와 reduce를 사용한 풀이

 

from collections import Counter
from functools import reduce

cnt = Counter([kind for name, kind in clothes])
answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1

 

이런 풀이를 봤는데 흥미로워서 가져와봤다.

사전 자료형을 이용해 종류별로 개수를 계산한 것을 Counter로

전체 가짓수를 곱해서 -1 하는 계산을 reduce 함수로 처리한 풀이이다.

복잡하므로 하나씩 살펴보자

   1. Counter

clothes = [["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]
clothes[0]	yellowhat	headgear
clothes[1]	bluesunglasses	eyewear
clothes[2]	green_turban	headgear

 (clothes 리스트 구성)

 

Counter는 이름 그대로 등장 횟수를 세는데 유용한 라이브러리이다.

위 코드를 해석해보면

clothes라는 list는 name과 kind로 구성되어 있는데, 이 중 kind를 기준으로 등장 횟수를 세주세요.

라는 말이다.

 

즉, closthes 안 각 item의 첫 번째 성분(yellowhat, blueglasses, green_turban)을 name으로,

두번째 성분(headgear, eyewaer, headgear)을 kind로 명명하고

이 중 두번째 성분인 kind를 기준으로 등장 횟수를 세서 cnt에 반환하는 코드인 것이다.

반환값은 다음과 같다.

 

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

   2. Reduce

 

reduce는 list 내부의 값을 중첩해서 하나의 반환값을 만드는 함수....라고 블로그에서 봤다.

예를 들어 [1, 2, 3]과 같은 리스트가 있고 lambda 함수로 x*y라는 함수를 준다면

1*2*3 = 6을 반환하는 함수인 것이다. (사실 이런 함수까지 알아야하나 싶다.)

 

answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1

 

풀이에서는 다음과 같이 쓰였는데 reduce 반환값을 만드는 방법으로 lambda 함수가, 

값이 들어있는 list로 cnt.values()가, 그리고 최초 초기값이 1로 지정되어있다.

즉, 위의 cnt 값을 가져오면 1(초기값) * (2 + 1) * (1 + 1) = 6이 나오고

여기서 아무 것도 입지않은 경우의 수 1을 뺀 값이 answer에 들어가는 것이다.

 

 

고찰

 

이 문제를 분류해보면 딱봤을 때 조합을 써야겠다라는 생각이 들기도하고

뭐...경우의 수를 구하는 문제로 분류할 수 있을 것 같은데

경우의 수는 확률과 통계에서도 했듯이

 

1. 전체를 계산한 후에 제외되는 항목을 빼거나

2. 일일이 하나씩 구해서 더하거나

 

이렇게 두 가지 풀이가 모두 나온다. 이 두 가지 풀이 중 계산하기 쉬운 것을 선택해서 풀어 나가는게 정답일 확률이 높다.

 

위 풀이들에서도 그러한 경향이 보이는데

1 + 2 + 3 + (1*2) + (1*3) + (1*2*3)과 같이 식을 세우는 것은 일일이 하나씩 구해서 더하는 방식이고,

각 가지수에 입지 않음을 추가 후 곱해 아무 것도 입지 않음을 제외하는 방법은 전체를 계산 후  제외 항목을 빼는 방법이다.

딱 봤을 때도 전체 계산 후 제외하는 방법이 훨씬 쉽다.

문제에서도 힌트를 준 것이 문제 조건 중

 

스파이는 하루에 최소 한 개의 의상은 입습니다.

 

라는 조건이 적혀있다.

경우에 수의 특성을 띄는 문제라는 것을 파악하고 두 가지 방법을 처음에 비교해보았다면 쉽게 풀렸을 문제이다.

다른 경우의 수 문제를 풀 때도, 두 가지 방법을 비교하는 습관을 들여야 할 듯.