99클럽 코테 스터디 2일차 TIL - 해시

오늘의 학습 키워드

해시
경우의 수

---

알고리즘 문제

• 프로그래머스 Level 2 - 의상
• https://school.programmers.co.kr/learn/courses/30/lessons/42578

---

공부한 내용

HashMap

• 키와 값을 쌍으로 저장하는 자료구조로 배열과 해시 함수를 사용한다.
• 키가 해시 함수에 의해 해시 값으로 변환 -> 해시 값으로 배열의 인덱스 매핑 -> 해시 값 인덱스에 키-값 저장
• 데이터 조회, 삽입 시 평균 O(1) 시간복잡도.

독립적 선택지의 경우의 수

• 선택지가 독립적이다: 각 선택 다른 선택에 영향을 주지 않는다는 의미.
• 문제에서 보면, 의상 타입별로 선택하는 데 독립적 => 모자를 어떤 것을 쓰든지 상의나, 하의, 다른 의상 타입 선택에 영향을 주지 않는다.
• (전체 경우의 수 - 제외할 경우의 수) 로 경우의 수를 구할 수 있다.
• 문제에 대입해서
  
  • 전체 경우의 수: 모자 선택의 경우의 수 * 상의 선택의 경우의 수 * 하의 선택의 경우의 수 
  • 제외할 경우의 수:  1 ( 모자, 상의, 하의 모두 선택하지 않는 경우 )

수학적 접근

• 의상 종류가 2개인 경우
  • e.g. 모자 - a개 / 상의 - b개
  • 경우의 수 : a, b, ab
  • 조합의 수 : (a + b) + (ab)
• 의상 종류가 3개인 경우
  • e.g. 모자 - a개 / 상의 - b개 / 하의 - c개
  • 경우의 수 : a, b, c, ab, bc, ac, abc
  • 조합의 수 : (a + b + c) + (ab + bc + ca) + (abc)
• 다항식 n차식 계수들의 합 (n : 의상 종류 개수)
  • 의상 종류 2개 (2차식) : (x+a)(x+b) = x**2 + (a+b)x + (ab)
  • 의상 종류 3개 (3차식) : (x+a)(x+b)(x+c) = x**3 + (a+b+c)x**2 + (ab+bc+ca)x + (abc)
  • 계수들의 합은 x에 1을 대입 
    • 모자/상의/하의 조합의 수 : (1+a)(1+b)(1+c) -1
    • -1은 x**3의 계수는 조합의 수[ (a + b + c) + (ab + bc + ca) + (abc) ]에 포함되지 않으니까 빼준다.

---

오늘의 회고

처음 시도

• "최소 의상은 1개 이상 입는다" 조건과 " 각 종류별로 1가지 의상만 착용할 수 있다" 조건으로 의상 종류 별 아이템 개수를 카운트하고 아이템 개수로 의상 조합 경우의 수를 계산해야겠다고 생각했다.
• 막상 경우의 수를 따져보니 의상 종류가 2개일 때는 쉬웠지만 3개일 때 맞는 경우의 수를 일일이 따져보니 복잡해졌고, 함수로 도출하기 어려웠다.

해결

• 경우의 수를 따질 때, 순서가 있지도 않고 선택에 서로 독립적인 부분이 있었다.
• 모든 경우의 수에서 경우의 수 1개( 한 개의 의상도 입지 않는 경우 )를 제외시키면 모든 조합을 계산할 수 있었다.

---

문제 풀이

HashMap

• HashMap 사용 이유: key에 의상 종류를, value 의상 종류에 해당하는 아이템 개수를 저장해서, 의상 종류 별 아이템 개수를 카운트하기 위해서.
• 시간복잡도: O(1)

경우의 수 계산

• 각 의상 종류 별로 여러 개 의상이 있을 수 있고, 1개만 있을 수 있다.
• 의상 조합의 수를 구하는 게 목표.
• 왜 의상 종류의 카운트에 +1을 해서 곱할까?
  • 먼저, 의상 종류별 선택에 대해 서로 독립적이다.
  • 각 타입별 경우의 수를 곱하면 전체 경우의 수가 나온다.
  • 의상 종류(모자, 상의, 하의) 별 카운트에 +1은 그 의상 종류를 입지 않는 경우를 포함하기 위해서이다.
  • 모자 선택 경우의 수: 모자 A, 모자 B, 아무것도 선택하지 않음 => 모자 개수 + 1 (모자 선택하지 않는 경우)
  • 상의 선택 경우의 수: 상의 A, 상의 B, 상의 C 아무것도 선택하지 않음 => 상의 개수 + 1 (상의 선택하지 않는 경우)
  • 하의 선택 경우의 수: 하의 A, 하의 B, 아무것도 선택하지 않음 => 하의 개수 + 1 ( 하의 선택하지 않는 경우)
• 그럼 왜 마지막에 -1을 할까?
  • 각 의상 종류 별로 입지 않는 건 괜찮다. 다른 의상을 선택한다면..
  • 모든 의상 종류를 하나도 선택하지 않는 경우는 " 최소 의상은 1개 이상 입는다" 조건에 위배되므로 전체 경우의 수에서 제외해야 한다. 
  • 따라서 계산된 경우의 수는 전체 경우의 수 - 1 (모자/상의/하의 모두 선택하지 않는 경우) 이다.
• github 풀이

Algorithm-Practice/프로그래머스/2/42577. 전화번호 목록/전화번호 목록.java at main · dev-jinius/Algorith

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        
        Map<String, Integer> map = new HashMap<>();
        
        for (int i = 0; i < clothes.length; i++) {
            if (map.containsKey(clothes[i][1])) {
                map.compute(clothes[i][1], (key, value) -> value + 1);
            } else {
                map.put(clothes[i][1], 1);
            }
        }
        
        for (String key : map.keySet()) {
            answer *= (map.get(key)+1);
        }
        answer -= 1;
        
        return answer;
    }
}

다른 풀이

HashMap.getOrDefault()

• getOrDefault(key, value): HashMap에 key가 존재하지 않으면 value를 기본값으로 반환한다.
• map.getOrDefault(clothes[i][1], 0) + 1: 의상 종류 key에 대한 카운트를 가져오고, 없다면 0 + 1, 이미 있다면 카운트+1

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        
        Map<String, Integer> map = new HashMap<>();
        
        for (int i = 0; i < clothes.length; i++) {
            map.put(clothes[i][1], map.getOrDefault(clothes[i][1], 0) + 1); 
        }
        
        for (String key : map.keySet()) {
            answer *= (map.get(key)+1);
        }
        answer -= 1;
        
        return answer;
    }
}