HashMap

백준 해시 해킹

• 그린닷컴의 운영자 연두는 비밀번호를 평문 그대로 저장하는 과오를 뒤로하고, 이제부터 암호에 해시 함수를 적용해 저장하려고 한다. 연두가 아는 해시 함수라고는 알고리즘 문제 풀이에 많이 사용되는 롤링 해시 함수밖에 없기 때문에 이것을 응용하여 사용하기로 했다.

그린닷컴의 비밀번호 규칙은 꽤 특이한데, 길이가 정확히
$N$이어야 하며, 비밀번호를 이루는 문자는 지정된
$M$개의 문자 중 하나여야 한다. 따라서, 사용 가능한 각 문자를
$0$부터 차례대로 정수에 대응시키면, 비밀번호를 길이가
$N$이고 모든 원소가
$0$ 이상
$M-1$ 이하인 배열
$P = [P_0, P_1, \dots, P_{N-1} ]$로 나타낼 수 있다.

이렇게 비밀번호를 배열
$P$로 나타낸 후, 미리 정해진 정수
$A$를 이용하여 다음과 같은 해시 함수
$h$를 적용한다.

$h(P) = (P_0 \cdot A^0 + P_1 \cdot A^1 + ... + P_{N-1} \cdot A^{N-1}) \mod M$ 

예를 들어 배열
$P = [10, 30, 20], A = 7, M = 55$인 경우를 생각해보자. 이 경우
$h(P) = (10 \cdot 7^0 + 30 \cdot 7^1 + 20 \cdot 7^2) \mod 55 = (10 + 210 + 980) \mod 55 = 45$이다. 여기서
$\bmod$는 나머지 연산으로
$1200 = 21 \cdot 55 + 45$이므로
$1200 \mod 55 = 45$이다. 따라서 해시값은 항상
$0$ 이상
$M-1$ 이하의 정수이다.

그린닷컴 관리자 계정의 비밀번호 해시값을 해킹한 재현이는, 이 해시값으로 실제 비밀번호가 뭐였는지 역추적해보려고 한다. 하지만 그린닷컴에서 사용 가능한 비밀번호는
$M^N$개나 있고, 이 중 과연 알아낸 해시값과 일치하는 비밀번호는 몇 개나 될지 궁금해졌다. 여러분이 이것을 대신 구해주자.

?

프로그래머스 의상

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

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

종류 이름
얼굴 동그란 안경, 검정 선글라스
상의 파란색 티셔츠
하의 청바지
겉옷 긴 코트
코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
코니는 하루에 최소 한 개의 의상은 입습니다.
코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

import java.util.*;
class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        
        Map<String, Integer> hm = new HashMap<>();
        
        for(int i=0; i<clothes.length; i++) {
            String key = clothes[i][1];
            hm.put(key, hm.getOrDefault(key,0)+1);
        }
        
        Iterator<Integer> it = hm.values().iterator();
        
        while(it.hasNext()){
            answer *= it.next().intValue() +1;
        }
        
        return answer-1;
    }
}

TIL

• hm.getOrDefault(key,0)+1
• Iterator it = hm.values().iterator(); map에서 value값만으로 iterator가능