코딩테스트 연습 - 위장

조합으로 풀기

문제 풀이 아이디어

들어오는 입력을 보면 [옷, 카테고리]의 배열이라고 볼 수 있습니다. 우리는 이 입력을 [카테고리:카테고리에 속한 옷의 갯수]의 형태로 바꾸어 주어야 문제를 해결할 수 있습니다.

이렇게 바꾼 이후에 조합을 통해서 1개의 카테고리에서만 옷을 고른 경우 ~ 모든 카테고리에서 옷을 고른 경우의 각각의 경우의 수를 계산해 더해주면 됩니다.

각각의 경우의 수는 (A 카테고리의 옷 종류) … (N 카테고리의 옷 종류)로 단순하게 곱하면 되므로 reduce문을 사용해서 계산해보겠습니다.

Dictionary의 default 값 설정하는 법

원래 key가 없는 경우에는 dict[key]는 nil을 반환하는데요. 아래 subscript를 활용해면 nil일 때 대신 반환할 default값을 정해줄 수 있습니다.

setter 또한 구현되어 있습니다. += 1을 하게 되면 dict[key]가 nil인 경우 기본값 0에 1을 더해 1이 되고 nil이 아닌 경우 dict[key]값에 1을 더합니다.

dict[key, default: 0]

dict[key, default: 0] += 1

코드

import Foundation

// 조합 구현
func combination(_ array: [Int], _ length: Int) -> [[Int]] {
    var result = [[Int]]()

    func combi(_ now: [Int], _ index: Int) {
        if now.count == length {
            result.append(now)
            return
        }

        for i in index..<array.count {
            combi(now + [array[i]], i + 1)
        }
    }

    combi([], 0)

    return result
}

func solution(_ clothes:[[String]]) -> Int {
    var dict = [String:Int]()

    // dictionary에 카테고리별 갯수 저장
    for clothes in clothes {
        dict[clothes[1], default: 0] += 1
    }

    var cnt = 0
    
    // 1개의 카테고리 ~ 모든 카테고리의 옷을 입는 경우의 각각의 경우의 수를 계산해서 더한다.
    for i in 1...dict.keys.count {
        for combi in combination(Array(dict.values), i) {
            cnt += combi.reduce(1, *)
        }
    }

    return cnt
}

안 입는 경우를 추가해서 풀기

문제 풀이 아이디어

위 문제를 채점해보면 조합 때문에 엄청나게 실행시간이 오래걸리고 1번 테스트 케이스의 경우 시간초과가 나옵니다. N이 30이기는 한데 재귀함수의 경우 이 정도 N도 부담스럽습니다.

하지만 발생을 전환하면 조합 없이 문제를 해결할 수 있습니다.

예를 들어 스파이에게 2개의 카테고리의 옷이 있고 각각 [A, B, C], [a, b]라고 해봅시다. 여기에 안 입는 경우를 추가하면 조합 없이도 모든 옷을 입는 경우의 수를 구할 수 있습니다. 즉 X(x)를 해당 카테고리의 옷을 안 입는 것이라고 하면 각각 [X, A, B, C], [x, a, b]이 되고 그냥 4 x 3 = 12로 12가지 경우의 옷 조합이 나옵니다.

하지만 우리 문제의 경우 최소한 1가지의 옷을 입어야 한다고 하였으므로 아무 것도 있지 않는 조합인 Xx를 빼주면 됩니다. 따라서 총 11가지의 경우가 되는 것이죠.

이렇다면 이제 간단합니다. dict.values에 각각 1을 더하고 모두 곱한 다음에 1을 빼면 되는 것이죠.

코드

import Foundation

func solution(_ clothes:[[String]]) -> Int {
    var dict = [String:Int]()
    
    for clothes in clothes {
        dict[clothes[1], default: 0] += 1
    }
		
		// value에 1씩 더하기    
    var cases = dict.values.map { $0 + 1 }
    
		// 모두 곱하고 1 빼기
    return cases.reduce(1, *) - 1
}