[프로그래머스/Lv.2 (Swift)] 의상

 

연습문제 > 의상

 

 

해당 문제는 해시테이블과 조합을 이용해야 합니다.

 

 

코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다.
예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.

착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나,
혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
(프로그래머스: 연습문제 > 의상)

 

 

 

해시 테이블을 사용하는 이유는,

아래와 같이 [의상 이름, 의상 종류] 형태의 입출력이 주어질 때

 

 

["의상 종류": 해당 의상의 개수] 만 파악해도

조합으로 계산이 가능하기 때문입니다.

 

 

해시테이블과 조합을 사용해야 한다는 점은 어렵지 않게 접근했지만,

조합을 직접 구현해야 한다는 생각에 매몰되어 불필요한 시간 초과를 반복했습니다.

 

 

 

 

❎ 첫 번째 아이디어:

생길 수 있는 경우의 수를 모두 파악하여, 경우의 수들을 count해 조합 계산

 

첫 번째 아이디어는 해시 테이블 또한 

["의상 종류": ["해당 의상들의 이름"]] 의 형태를 띄고 있어야 하며,

조합을 계산하기 위한 시간 복잡도가 많이 듭니다.

 

 

 

✅ 두 번째 아이디어:

각 key에 대한 value에 아예 착용하지 않는 경우를 포함

 

각 악세서리는 쓰거나 / 쓰지 않는 경우로 나뉘어지고,

쓰는 경우에 n가지의 종류로 나뉘어집니다.

 

따라서, 쓰지 않는 경우 또한 선택지로 +1 해주면 간단합니다.

 

조합에 대한 모든 경우의 수를 구할 필요가 없고,

위 예시의 경우, 3 * 2 * 3 - 1 (모두 쓰지 않는 경우 빼기)를 하면

간단하게 답이 나옵니다.

 

 

---

 

 

어렵지 않은 문제였지만,

수학적 사고를 잊지 말자는 의미로 기록을 남깁니다. 😅

 

 

 

프로그래머스: 연습문제 > 의상

 

import Foundation

func solution(_ clothes:[[String]]) -> Int {
    
    var clothesDict: [String: Int] = [:]
    
    for c in clothes {
        clothesDict[c[1], default: 0] += 1
    }
        
    var keys = clothesDict.keys
    var result = 1
    
    for c in clothesDict {
        if keys.count == 1 { 
            return c.value
        } else {
            result *= (c.value + 1)
        }
    }
    
    return result - 1
}