Lv2 위장

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

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

분류: Lv2 해시

---

처음엔 쉬워보였지만 개인적으로 꽤 어려웠던 문제였습니다...

"중복된 이름은 없으니 분류별로 개수만 카운팅하면 되겠다" 라고 생각하며 접근했지만 그 이후 경우의 수를 어떻게 계산해야 할 지가 문제였습니다. 

단순히 종류별 개수로 곱하면 경우를 다 포함하지 못하고..

종류별로 1개를 뽑는 경우, 2개를 뽑는 경우 ... 로 나눠보자니 종류별로 개수가 다르고..

결국 다른 분들의 풀이를 찾아보았습니다. 

이 문제의 가장 큰 포인트는 의상을 최소 1개만 선택하면 더 이상을 뽑지 않아도 된다는 것입니다. 1개만 뽑으면 나머지는 선택사항이 되는거죠. 따라서 그 선택 사항을 추가해주는 것입니다. 종류별로 뽑지 않아도 되는 경우를 추가해 모든 경우의 수를 구하고 아무것도 뽑지 않았을 경우 1가지만 빼주면 가능한 모든 경우의 수를 구할 수 있습니다. 

첫 번째 예를 살펴보면, "headgear", "eyeweare" 2 종류가 있는데 편의상 a, b로 생각하겠습니다. 

그러면 a: 2, b: 1의 가지 수가 있고 여기에 각 종류별로 뽑지 않아도 되는 경우를 추가해서 경우의 수를 구하면

(a+1) * (b+1) = (2+1) * (1+1) = 6가지 

입니다. 

여기에 아무것도 뽑지 않은 경우의 수 1을 빼주면 답이 됩니다.

(a+1) * (b+1) - 1 = 5가지

 

구현

import Foundation

func solution(_ clothes:[[String]]) -> Int {
    
    var items: [String: Int] = [:]
    var result = 1
    
    for clothe in clothes {
        let kind = clothe[1]
        
        if items[kind] == nil {
            items[kind] = 1
        } else {
            items[kind]! += 1
        }
    }
    
    items.map {
        result *= ($1 + 1)
    }
    
    return result - 1
}

 

회고

경우의 수 문제는 항상 어렵다.. 선택일 경우에 선택하지 않았을 경우의 수 추가할 수도 있음을 배웠다. 경우의 수는 모든 경우를 생각하고 예외가 어떤 것이 있을지 생각하는 연습이 필요할 것 같다.