Lv.2 [Hash] - 의상(위장)

---

[ 문제 링크 ]

프로그래머스 Lv2. 의상(위장)

[ 문제 설명 이미지 ]

 

 

 

 

의상(위장)

스파이가 위장할 수 있는 아이템들의 종류가 있다.
각 종류들을 조합해서 위장을 하게 되는데, 그 모든 경우의 수가 몇가지가 되는가
위장 용품은 착용을 할 수 있고 안할 수도 있다.
쉽게 접근하면 위장용품들의 각 갯수를 서로 곱하면 모든 경우의 수가 나온다.
하지만 착용 안할 수도 있다.
경우의 수에 1을 더해서 모두 곱해주면 된다.
모든 위장용품을 하나도 착용하지 않은 경우가 포함되기 때문에 추후 1을 빼주면 된다.

문제의 핵심은 경우의 수를 구하는 것이 아니라 아이템의 종류별로 갯수를 카운트하는데에 있다.
문제에서는 헤드기어 2종류, 아이웨어 1종류가 있다.
종류별로 총 몇개가 나오는지를 카운트 하는것이 이 문제의 핵심이다.
배열 몇개를 만들어 각 종류별로 인덱스를 나누어서 저장히여 카운팅할 수 있다.
그러나 종류가 정해져있지 않으므로 구현할 수가 없다.
이런 경우 인덱스가 아닌 키값으로 정보를 저장할 수 있는 해쉬를 사용하는것이 좋다.

배열에서의 특정 값에 대한 탐색은 순차적으로 매번 인덱스에 접근해야 하므로 비효율적이다.
해쉬에서는 키:값을 사용한다
키로부터 해쉬값을 얻어 해쉬값을 인덱스로 사용하는 것이다.
언제든 해쉬값만 얻을 수 있다면, 탐색없이 인덱스로 바로 접근이 가능해진다.
해쉬값은 해시함수를 통해 얻은 값을 말하는데, 해시함수란? 최대한 겹치는 값이 발생하지 않도록 유니크값을 생성해는 함수이다.
특정 키의 해시값을 얻어 그것을 배열의 인덱스로 사용하는 자료구조이다.
해시의 자료구조 구성 :배열, 리스트, 탐색, 해시

Hash

위장 문제에서는 위장 아이템의 종류별로 갯수를 세는것이 핵심이다.

자료구조는 Hash를 사용하는 자료구조가 중점이므로 HashMap을 사용한다.

갯수

<키: 종류 / 값:갯수>

---

[풀이 1] 

class Solution {
    public int solution(String [][] clothes) {
        int answer = 1;
        int len = 1;
        Map<String, Integer> counts = new HashMap<>();
        for (String[] clothe : clothes) {
//            counts.put(clothe[1], counts.get(clothe[1]) == null ? 0 : counts.get(clothe[1]) + 1); // 0이라면 0 + 1 에대한 값저장 아니라면 현재값+1에 대한 값 저장
//            counts.put(clothe[1], counts.getOrDefault(clothe[1], 0) + 1);
            if (counts.containsKey(clothe[1])) len++; // 존재하면 1 증가 => 다른종류가 될 수 있는 이전값에 대한 누적증가를 하기 때문에 안된다.
            counts.put(clothe[1], len);
        }
        for (Integer value : counts.values()) {
            answer *= (value+1);
        }
        answer -= 1;
        return answer;
    }
}

종류별 의상 갯수를 모두 곱하면 의상을 조합하는 모든 경우의 수가 나온다.

이때, 각 종류별 갯수에 1을 더해서 곱해주면, 각 종류별로 입지 않은 경우까지 처리가 가능하다.

단, 모든 경우의 수가 나왔을 경우 아무것도 입지 않은 경우에 대한 값 1을 빼는것이 핵심이다.

---

[풀이 2] Stream 사용

import java.util.stream.IntStream;

public class Solution {

   public int solution(int[][] clothes) {
        return Arrays.stream(clothes)
        .map(clothe->clothe[1]) // 의상 종류 추출
        .distinct() // 중복제거
        .map(kind-> //중복제거된 종류를 기준으로 일치하는 옷의 갯수 + 1(입지 않은경우)
        	(int) Arrays.stream(clothes).filter(clothe->clothe[1].equals(kind)).count() + 1
        ).reduce(1, (c, n) -> c * n) //초기값 1 기준 누적곱 연산. C의 초기값은 1이다.
        - 1;
    }

}