프로그래머스 위장 - 인수분해

skyepodium·2022년 2월 7일
0

정말 해시 문제인가

뭔가 잘 풀리지 않았다.

개인적으로 해시의 비중이 커 보이지 않는다.

어떻게 조합의 개수를 어떻게 구하지 문제인것 같다.

다른 글을 보았을 때 조합의 개수 구하는 공식이 (x + 1)(y + 1) - 1 이라고 합니다.

근데 그거 어떻게 구하지...

1. 조합의 개수 그거 어떻게 구하지

문제의 예시대로 다음과 같이 있으면

  • head_gear - 2개
  • eye_wear - 1개

조합의 개수는

head_gear + eye_wear + head_gear * eye_wear

조금 더 간단하게 표현하면
x + y + xy

자 중학교 때로 돌아가보면

뭐 이런것 배웠던 것 같다.

x + y + xy 에서

두 개의 항으로 묶습니다.
x(y + 1) + y

공통인수로 묶어야 하는데... 어디에서 1을 빌려옵시다.
x(y + 1) + (y + 1) - 1

공통인수 y+1로 묶어줍니다.
(x + 1)(y + 1) - 1

사실, 3개부터는 힘들다.

x + y + z + xy + yz + xz + xyz

x(1 + y) + y(1 + z) + z(1 + x) + xyz
x(1 + y + yz) + y+yz + z + x

x(1 + y + yz) +(1 + y+ yz) - 1 + z + x
(1 + y + yz)(x + 1) +x + z -1

안할래요 못하겠어요.

2. 인수분해

나무공학 위키에 따르면 인수분해는 어떤 원소를 다른 원소의 곱으로 표현하는 것

그리고, 미리 외워서 써먹는 것이 정신 건강에 이롭다.

하나만 기억합시다. 모두
x + y + xy-> (x+1)(y+1) - 1

3. 코드

반항심에 숏코딩 하려고 했는데 그것마저 잘 안된다.

1) python

from collections import defaultdict

def solution(clothes):
    # 1. 초기화
    d = defaultdict(int)
    res = 1

    # 2. 카운트
    for c, t in clothes:
        d[t] += 1

    # 3. 인수분해
    for x in d.values():
        res *= (x+1)

    return res - 1

2) java

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int solution(String[][] clothes) {
        // 1. 초기화
        int res = 1;
        Map<String, Integer> m = new HashMap<>();

        // 2. 카운트
        for(String[] c: clothes) {
            m.put(c[1], m.getOrDefault(c[1], 0) + 1);
        }

        // 3. 인수분해
        for(Integer x: m.values()) {
            res *= (x + 1);
        }

        return res - 1;
    }
}
profile
callmeskye

0개의 댓글