프로그래머스> 해시> 위장

 

<문제링크: https://programmers.co.kr/learn/courses/30/lessons/42578>

코딩테스트 연습 - 위장

 

문제설명: clothes배열 안에 아이템 이름과 아이템 종류가 배열로 들어있는 2차원 배열 형태이다. 같은 종류 중 1개의 아이템만 사용하여 총 몇가지의 조합을 만들 수 있는 지 구하는 문제이다. 단, 아무것도 선택하지 않는 경우는 없다.

 

 

[1차 시도]

def solution(clothes):
    answer = 1
    bin = {}
    for c in clothes:
        if c[1] not in bin:
            bin[c[1]] = [c[0]]
        else:
            bin[c[1]].append(c[0])
    for k,v in bin.items():
        answer*=len(v)+1
    return answer-1

 

풀이: 먼저 clothes배열을 돌면서 아이템 종류별(key)로 아이템들(value)을 배열로 저장하기 위해 빈 dictionary를 만들어 사용했다. 처음부터 다 돌고 시작하면 시간초과가 날까 걱정했지만, 다행히 시간초과는 안났다. dictionary에 넣어둔 key와 value 중 value의 길이 즉 아이템 종류별 아이템의 개수+1을 해서 모두 곱해준다.

이렇게 하는 이유는 각 아이템 종류별 선택지는 입거나 안입거나 둘 중 하나이므로 총 아이템 개수 +1을 해서 안 입는 선택지도 같이 포함시켜줍니다. 다 곱해준 후 마지막에 answer에서 모두가 안 입는 선택지였던 1개를 빼주면 된다.

 

채첨결과: 정확성, 효율성 모두 정상적으로 잘 통과한다.