[3주차] 1. 위장

문제 설명 및 풀이 방식

이 문제는 옷의 종류별 조합이 몇가지나 되는지 구하면 된다

위장 용품 종류 별 갯수를 구해서 곱해주면 전체 조합을 구할 수 있다

이 때 위장 용품 착용을 안할수도 있으니까 각각의 위장용품 종류 + 1을 햇 곱해준다

근데 이렇게 하면 아무것도 착용 안한 경욱 있으니까 그 경우를 하나 빼줘야 한다

 

이 문제의 핵심은 위장 용품의 종류 갯수를 세는 것에 있다!

이를 세기 위해서 해시를 이용한다

 

 

<Hash>

해시는 인덱스가 아닌 키 값을 저장할 수 있는 자료구조이다

특정 key의 hash 값을 얻어서 그걸 배열의 index로 사용하는 자료구조이다

이 때 hash 함수는 최대한 겹치는 값이 없도록 unique한 값을 생성하는 함수이다

또한 해시는 탐색 없이 인덱스(key)값으로 바로 value에 접근이 가능해서 자주 사용된다!

해시 -> 배열, 리스트, 탐색, Hash 자료구조로 구성되어 있어서 면접 질문에도 자주 나오니까 잘 알아두자!

 

 

이제 코드를 보자!

 

 

 

자바 코드)

import java.util.*;
public class comu1 { //위장
    static public int solution(String[][] clothes) {
        int answer = 1;
        Map<String,Integer> counts = new HashMap<>();

        for(String[] c : clothes) {
            String type = c[1]; //옷의 종류

            // type을 key로 갖는 value를 조회해서
            // 만약 null인 경우에는 default 값으로 0을 저장하고
            // null이 아니면 해당 값에 1을 더해라
            counts.put(type, counts.getOrDefault(type, 0)+1);
        }

        for(Integer c : counts.values()) {
            answer *= c + 1;
        }

        answer -= 1;
        return answer;
    }


}

자바에서는 Hash 자료구조를 Map으로 사용한다

Java에서 Map은 인터페이스이기 때문에 new로 생성이 안되고, Map 인터페이스를 구현한 Object를 생성해줘야 하는데 여기서는 HashMap을 사용할 것이다!

그리고 getOrDefault 함수를 이용해서 추가해주고 나머지 알고리즘은 동일~