(파이썬) [알고리즘 문제 풀이] - 위장 (프로그래머스)

오늘은 프로그래머스에서 위장이라는 문제를 풀어 보았습니다.

 

Input은 옷의 종류와 이름이 담긴 배열로 주어집니다.

 

옷의 종류는 중복이 있을수 있으나 옷의 이름은 모두 다릅니다. 

 

예를 들면 같은 하의 라도 청바지가 있고 반바지가 있을수 있습니다.

 

이 부분을 보시면 떠오르는 자료구조가 있을껍니다.

 

파이썬에는 key와 value로 이루어진 dictionary가 있습니다.

 

옷의 종류가 key가 되고 옷의 이름이 value가 된다고 생각하시면 됩니다.

 

여기까지 왔으면 이 문제의 반은 해결했다고 보시면 됩니다.

 

이제부터 모든 경우의 수를 계산해야 되는데 매우 간단합니다.

 

만약 옷의 종류가 A,B,C 이렇게 3가지가 있다면,

(A 타입의 옷의 개수 + 1) * (B 타입의 옷의 개수 + 1) * (C 타입의 옷의 개수 + 1) - 1 = 모든 경우의 수

각 종류마다 옷의 개수에 1을 더하고 서로 곱한 다음에 마지막에 1을 빼면 됩니다.

 

 

여기서 왜 종류마다 1을 더해야 하는지?

여기서 +1은 해당하는 종류의 옷을 입지 않는 경우 입니다.

예를 들어, A 종류의 옷은 입지 않고 B 종류의 옷과 C 종류의 옷을 입는 경우 입니다.

 

모두 곱한 값에서 마지막에 1은 왜 빼는걸까?

최소 한개의 옷은 입어야 함으로,

아무것도 입지 않는 경우를 제외 시켰습니다.

 

그래서 알고리즘을 코드로 옮기면,

def solution(clothes):
    answer = 1
    types = dict()
    
    for item in clothes:
        if item[1] in types:
            types[item[1]] += 1		#이미 사전에 등록되어 있는 종류의 옷
        else:
            types[item[1]] = 2	#사전에 아직 등록 안된 종류의 옷
            
    for value in types.values():
        answer *= value		#모든 경우의 수
        
    return answer-1		#모든 경우의 수에서 아무것도 안 입는 경우를 빼고 리턴

아직 dictionary에 등록되지 않은 종류의 옷은 시작 값을 2로 설정했습니다.

 

1이 아니라 2인 이유는 해당 종류의 옷을 입지 않는 경우도 포함해야 하기 때문입니다.

 

그리고 같은 종류의 옷을 발견할때마다 그 종류의 값에 +1을 합니다.

 

dictionary 자료 구조를 사용하셨다면 문제를 푸는데에 전혀 어려움이 없으셨을꺼라 생각합니다.