[Hash] 프로그래머스 코딩테스트 연습문제 Hash 3번 위장 JAVA 풀이

import java.util.HashMap;
class Solution {
    public int solution(String[][] clothes) {
        
        HashMap<String,Integer> map = new HashMap<>();
        int answer = 1;
        for(int i = 0 ; i < clothes.length;i++)  map.put(clothes[i][1],map.getOrDefault(clothes[i][1],0)+1);
        for (int i:  map.values())  answer*=(i+1);
        return answer-1; //하나도 안입은 경우 제외
        
    }
}

 

해시맵의 특성인

1. 키는 중복 불가

2. keySet(), values() 등을 통해 배열을 구하는 매소드가 존재

함을 이용하면 매우 쉽게 풀 수 있는 문제였다.

 

왜 i+1을 해주는가? +1은 바로 '아무것도 안입었을 경우'를 의미한다.

 

즉 종류가 2,2,2였을 경우. 그 종류의 옷을 안입은 경우를 고려해 3*3*3 = 27을 계산한다.

하지만 정말 아무것도 안입은 경우는 존재하지 않기에 -1을 해주면 된다.

 

위의 시간복잡도는 O(nlogn)이다. HashMap tree의 전체 순회가 필요하기 때문이다.

트리에서의 삽입과 삭제는 logn이면 가능하다.

 

테스트 결과 ^^