[프로그래머스] LV2. 의상 - Swift

 

 

처음에 생각했던 풀이

1.  딕셔너리 생성 = "의상의 종류":["의상이름"] 
2. 범위 (1...의상의 종류 수) dp 테이블 만들기

3. dp 테이블 결과 반환

 

이 순서대로 그림을 그리고 규칙을 찾아 dp 테이블을 만들어 해결하려 했었다..

규칙을 찾고 싶었는데, 감만 오고.. 생각했던 대로 해결되지 않아서 "프로그래머스의 질문하기"를 확인해봤는데 명쾌한 수학적 풀이가 있어서 기록해두고자 한다.

 

고등학생 때 이 문제를 봤으면 좀 더 빠르게 해결방식을 알아냈을 듯 하다,,ㅎ.ㅎ

 

해결 방식

의상의 종류 1가지 상의일 경우 반환값 = 상의 개수     (아래부턴 편의상 "개수" 생략)

의상의 종류 2가지 상의, 하의일 경우 반환값 = 상의 + 하의 + 상의 * 하의

의상의 종류 3가지 상의, 하의, 신발일 경우 반환값 = 상의 + 하의 + 신발 + 상의 * 하의 + 하의 * 신발 + 상의 * 신발 + 상의 * 하의 * 신발

 

보기 쉽게 다시 작성해보면 아래와 같다.

의상의 종류 2가지 x, y일 경우 반환값 = x + y + xy

의상의 종류 3가지 x, y, z일 경우 반환값 = x + y + z + xy + yz + xz + xyz

 

 

이런 전개방식과 유사한 일반화 방정식을 하나 살펴보자..!

(x+1)(y+1)(z+1) = xyz + xy + yz + xz ++ x + y + z + 1

 

위에서 본 의상의 종류 수에 따른 반환값과 유사해보이지 않나요?!!!!!!

우리가 원하는 건 "xyz + xy + yz + xz ++ x + y + z" 이다!

 

xyz + xy + yz + xz + x + y + z = (x+1)(y+1)(z+1) - 1

 

따라서 위의 방정식처럼 치환해보면 우리가 원하는 결과는 방식은 (x+1)(y+1)(z+1) - 1 를 계산하면 된다는 것을 알 수 있다.

이를 일반화해본다면 다음과 같다.

(1번째 종류의 의상 개수 + 1) ... (n번째 종류의 의상 개수 + 1) - 1

 

이제 문제로 돌아가자!

---

이제 문제를 풀이하는 방법을 다음과 같이 세 단계로 정의할 수 있을 것이다.

1. 딕셔너리 생성 = ["의상의 종류":["의상이름"]]

2. 반복문으로 딕셔너리를 돌면서 (value.count + 1)를 ans 변수에 곱해주기

3. ans - 1 반환

 

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

    var dic: [String: [String]] = [:]
    for cloth in clothes {
        if dic[cloth[1]] == nil {
             dic[cloth[1]] = [cloth[0]]
        } else {
            dic[cloth[1]]!.append(cloth[0])
        }
    }
    
    for d in dic {
        ans *= d.value.count + 1
    }
    return ans - 1
}