[ 프로그래머스 ] 의상

 

 

🍄 프로그래머스 문제

프로그래머스

✍🏻 문제 풀이 Github 링크

-Swift-CodingTest/프로그래머스/2/42578. 의상 at main · BaeJihae/-Swift-CodingTest

 

 

 

문제 설명

코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.

예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다.

 

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

 

• 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
• 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
• 코니는 하루에 최소 한 개의 의상은 입습니다.

 

코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

 

 

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 코니가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.

 

 

입출력 예

clothes	return
[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]]	3

 

 

문제 풀이

 

나의 풀이

import Foundation

func solution(_ clothes:[[String]]) -> Int {
    
    var clothesDic = [String:Int]()
    
    clothes.forEach{ clothesDic[$0[1]] = ( clothesDic[$0[1]] ?? 0 ) + 1 }
    
    return clothesDic.values.reduce(1) { $0 * ($1 + 1) } - 1
}

 

보자마자 딕셔너리 문제라는 것을 깨달았다.

 

처음에는 딕셔너리를 [String: [String]]으로 정의하여 [의상의 종류: [의상의 이름]] ( 의상의 종류에 따른 의상의 이름 배열 )을 담았다. 하지만, 경우의 수를 구하는 과정에서 굳이 의상의 이름 배열이 아닌 의상의 종류에 따른 의상 갯수만 들어가도 된다는 것을 깨닫고, [String:Int]로 변경했다.

 

의상을 고르는 경우의 수를 구하는 것은 쉬웠다. 곱의 법칙을 활용해 문제를 푸는 것과 동일했다. 윗옷 2벌, 아래옷 3벌이 있을 경우엔 옷을 고르는 경우의 수가 23이므로 6이다. 위의 문제는 윗옷을 안입을수도 아래옷을 안입을 수도 있다는 가정이 내제되어 있기 때문에 (2+1)(3+1)의 경우의 수를 사용하면 되었다. 하지만, 무조건 옷을 한 개 이상은 입어야한다는 가정이 있기 때문에 하나를 빼준다.

 

 

다른 사람 풀이

import Foundation

func solution(_ clothes:[[String]]) -> Int {
    let types = clothes.compactMap({ $0.last })
    let typeSet = Set(types)
    let categories = Array(typeSet)

    let counts = categories.map({ category in
        return clothes.filter({ $0.last == category }).count + 1
    })

    return counts.reduce(1,  { $0 * $1 }) - 1
}

 

let types = clothes.compactMap({ $0.last })
// 	["headgear", "eyewear", "headgear"]

let typeSet = Set(types) // 중복값 제거
// ["headgear", "eyewear"]

let categories = Array(typeSet) // 다시 array로 변환
// ["headgear", "eyewear"]

 

위의 과정을 통해 의상의 종류 배열을 얻고, 이 배열을 이용해 각 종류에 따른 옷의 갯수를 map과 filter를 통해 구하였다. 경우의수를 구하는 과정은 나랑 동일했다.

 

 

위의 풀이를 압축시킨다면 아래의 풀이가 될 것이다.

func solution(_ clothes:[[String]]) -> Int {
    let counts = Set(clothes.compactMap({ $0.last })).map({ category in
        return clothes.filter({ $0.last == category }).count + 1
    })

    return counts.reduce(1,  { $0 * $1 }) - 1
}

 

 

🤔 그렇다면 이 문제는 배열이 빠를까 딕셔너리가 빠를까…?

 

나의 풀이인 딕셔너리가 빠르다는 판단을 했다.

 

배열로 푸는 과정에서 filter 연산을 사용하면 각 요소에 대한 실행을 하기 때문에 시간 복잡도가 높아진다. 또한 매번 filtering을 거쳐야 하므로 추가적인 계산이 많아진다. 각 종류마다 모든 배열을 다시 한번더 검색을 해야하므로 최악의 경우 O(n^2)의 시간 복잡도를 가진다.

 

그에 비에 나의 풀이인 딕셔너리는 clothes를 관찰하여 딱 한번의 O(n) 과정으로 딕셔너리를 업데이트한다.