[프로그래머스] Swift 위장 - 42578

✅ 이번시간에는 위장 문제에 대해서 알아볼까해.

 

처음에는 재귀로 풀었는데, 다른건 다 맞는데 테케 1번에서 시간초과가 나서 다른 알고리즘으로 바꿨다.

내가 과연 이걸 생각할 수 있을까 싶으면서도 가능하다고 해봐야지

 

✅ 주안점

1️⃣ 이번에 compactMap, flatMap도 확실하게 공부했고,

2️⃣ 딕셔너리에서 contains 쓰는 방법도 그동안 못했는데 확실히 했고,

3️⃣ 재귀 공부하면서 순열 조합 알고리즘도 공부했어서, 따로따로 다 정리할 예정.

 

//
//  main.swift
//  algorithm
//
//  Created by Hamlit Jason on 2021/11/02.
//

/* 더 맵게
 https://programmers.co.kr/learn/courses/30/lessons/42578
 */

import Foundation

func solution(_ clothes:[[String]]) -> Int {
    
   // 1. 카테고리별로 갯수가 몇개인지 찾아야 한다. 
   // 즉 카테고리 재정리한다.
    
    var category = [String:Int]() // 딕셔너리 선언
    
    // 카테고리에 들어있고, 같은 카테고리이면 +1, 그렇지 않으면 1로 추가한다.
    for i in clothes { 
        if category.contains(where: { (key,value) -> Bool in // 딕셔너리에 들어있는지 검사
            // 조건 검사
            return key == i[1] // 이 조건일때 true return 
        }) { // true이면 실행
            // if 문에 걸림 조건이 만족하면 실행된다.
            category[i[1]]! += 1
        } else { 
            category[i[1]] = 1
        }
    }
    
    
    // 2. value를 arr로 사용하기 위해 바꿔준다.
    var arr = [Int]() 
    
    category.values.forEach {
        arr.append($0)
    }
    
    
    // 3. 재귀로 푸는거 도전해보자. -> 재귀로 1번 자꾸 시간초과나서;; 이 코드는 블로그에 따로 적어두자
    var sum2 = 0
    arr = arr.map{$0+1}
    sum2 = arr.reduce(1) {$0 * $1}
    return sum2 - 1
}

 

🔶 3번 핵심 알고리즘 설명

왜 저렇게 되냐면 카테고리가 A,B,C 이렇게 3개의 카테고리가 있다고 하자.

그러면 옷을 입을 수 있는 경우의 수는

A, B, C , AB, AC, BC, ABC 이렇게 되고, 이 경우의 수를 전부 더하면 정답이 된다.

 

여기서 우리가 발견할 수 있는 수학식이 있는데, 

바로바로!!

(A+1)(B+1)(C+1) - 1 = A+B+C+AB+AC+BC+ABC 라는 것이다.

 

응...?

 

카테고리별 옷의 갯수를 A, B, C에 넣어서 계산해주면 끝!

 

그러니까 메인 아이디어는 (A+1)(B+1) ... (Z+1) - 1 의 알고리즘을 생각해 낼 수 있냐는 것이였다.

 

🔶 하지만 나는 이 식을 처음에 생각해내지 못해서, 재귀를 통해, A, B, C , AB, AC, BC, ABC를 한번씩 다 만들어보는 방법을 사용했다.

이때 사용한 알고리즘은 우리가 확률과 통계 시간에 배웠던 조합이라는 것이다. 

 

N개의 카테고리에 T개를 선택하는 방법으로 설계해서 풀었으나,

테스트케이스 1번을 시간초과로 통과하지 못해 알고리즘을 변경하였다.

 

물론 순열 조합에 대한 아이디어 즉, 재귀로 구현한 것은 따로 포스팅 하도록 하겠다.

 

 

 

아무튼 결과는 통과!

 

 

(참고)

 

https://jinshine.github.io/2018/12/14/Swift/22.%EA%B3%A0%EC%B0%A8%ED%95%A8%EC%88%98(2)%20-%20map,%20flatMap,%20compactMap/ 

[Swift] 고차함수(2) - map, flatMap, compactMap - jinShine