Programmers - Hash [위장]

1. 문제

문제 설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

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

종류이름

얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

clothesreturn

[[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgear]]	5
[[crow_mask, face], [blue_sunglasses, face], [smoky_makeup, face]]	3

입출력 예 설명

예제 #1
headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

1. yellow_hat 2. blue_sunglasses 3. green_turban 4. yellow_hat + blue_sunglasses 5. green_turban + blue_sunglasses

예제 #2
face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

1. crow_mask 2. blue_sunglasses 3. smoky_makeup

 

2. 내 풀이 

Java

import java.util.HashMap;

public class Camouflage {
    public int solution(String[][] clothes) {
        int answer = 1;

        HashMap<String, Integer> clothName = new HashMap<>();
        HashMap<String, Integer> clothType = new HashMap<>();

        for (int i = 0; i < clothes.length; i++) {
            // 옷 이름이 이미 있으면 카운트 추가 해당 옷이 없으면 넣고 카운트 1
            clothName.put(clothes[i][0], clothName.getOrDefault(clothes[i][0], 0) + 1);
            // 옷 종류가 이미 있으면 카운트 추가 , 해당 옷이 없으면 넣고 카운트 1
            clothType.put(clothes[i][1], clothType.getOrDefault(clothes[i][1], 0) + 1);
        }


        for (String type:clothType.keySet()) {
            int count = 0;
            for (int i = 1; i < clothType.size(); i++) {
                count += i;
            }
            answer = (int) (count * Math.pow(2, clothType.size()));
        }

        if (clothType.keySet().size() == 1){ return clothes.length; }
        return clothes.length + answer;
    }
}

- 못풀었다. 거의 다 푼것 같았는 데 경우의수를 세는 방법을 몰랐다..

- 너무 부끄럽다.

---

JS

function solution(clothes) {
    let clothesCount = new Map();
    // clothes 배열을 받은 다음 clothesType목록만 추가 시킴
    for(let i = 0; i < clothes.length; i++){
        // 만약 옷 종류가 등록 되지 않았다면 [옷 종류,  1] 추가
        if(!clothesCount.has(clothes[i][1])) clothesCount.set(clothes[i][1], 1);
        else{
            // 만약 옷 종류가 등록이 되어 있는 경우라면 [옷 종류 ,기존에 들어 있던 옷 종류의 갯수  + 1] 로 map 최신화
            clothesCount.set(clothes[i][1], clothesCount.get(clothes[i][1]) + 1);
        }
    }

    let answer = 1;
    
    // map의 keys()는 키들의 집합, values()는 값들의 집합
    // of 라는 표현은 foreach같은 표현 , 반복 가능한 객체를 하나씩 떠서 반복문 안에 넣는다.
    for(let a of clothesCount.values()){
        answer *= (a + 1);
    }
    return answer - 1;
}

let clothes = [['yellow_hat', 'headgear'], ['blue_sunglasses', 'eyewear'], ['green_turban', 'headgear']];
console.log(solution(clothes));

Map 객체

- js에는 hashmap처럼 쓸수 있는 Map이라는 객체가 존재한다.

- key와 value값을 가지며 key는 하나의 value값만을 가진다.

 

길이

- map의 길이는 size로 구할 수 있다. map.lenght는 0이다.

초기화

- map.clear()

키 제거

- map.delete(key) : 해당하는 키에 대한 value값이 제거 되고 map.has(key) 값이 반환된다.

키 참조

- map.get(key) : 해당하는 키에 대한 value값을 반환한다.

키값이 존재하는지

- map.has(key) : 해당하는 키가 존재하면 true, 존재하지 않으면 false를 반환한다.

키 set

- map.keys() : 객체안에 존재하는 모든키들을 iterator 객체로 반환한다.

값 set

- map.values() : 객체안에 존재한는 모든값들을 iterator 객체로 반환한다.

키, 값 추가

- map.set(key, value) : 해당하는 키에 value값을 집어넣고 최신화된 map을 반환한다.

 

developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Map

Map

for of 구문

- for of 구문은 반복가능한 객체를 반복문에서 사용자 정의 반복 후크를 적용할 수 있는 구문이다.

- java식 foreach 같다.

for(let a of array){
	console.log(a)
}
// array값을 하나씩 뽑아내서 출력한다.

Set 객체

- 중복을 제거하는 python의 set과 개념이 같다.

- 중복되는 값이 제거된다. 

- 중복되는 set 객체를 다시 배열로 바꿀때에는 전개연산자(Spread)를 사용할 수 있다.

let arr = [1, 2, 3, 3 ,3];
let set = new Set(arr);
for(let a of set){
    console.log(a);
}
//1
//2
//3

let newArr = [...set];
// spread of 문법
// set객체는 객체안의 속성을 펼친다음 []로 묶어서 배열로 만들었다.

 전개연산자 (Spread)

- js에만 있는 특이한 문법인데 객체 안의 내용을 모두 풀어내어 버린다.

- 위 예시와 같이 객체 앞에 ...라는 표현을 사용한다.

let arr = [1 ,2, 3];
let arr2 = [1, ...arr, 2, ...arr, 3];
console.log(...arr2);
//1 1 2 3 2 1 2 3 3

- 이는 객체에서도 마찬가지인데, 객체에서 전개연산자를 다음과 같이 사용할 수 있다.

- 객체안의 요소를 모두 풀어서 객체안에 집어 넣을 수도 있다.

const obj1 = {
	name : "name"
};

const obj2 = {
    ...obj1,
    age : 17,
};
const obj3 = {
    ...obj2,
    weight: 121
};

console.log(obj3);
//Object {name: "name", age: 17, weight: 121}

 

3. 다른 사람 풀이 

import java.util.HashMap;

public class Camouflage {
    public int solution(String[][] clothes) {
        int answer = 1;

        HashMap<String, Integer> clothType = new HashMap<>();

        // 옷 종류에 따른 옷 갯수 구하기
        for (int i = 0; i < clothes.length; i++) {
            // 옷 종류가 이미 있으면 카운트 추가 , 해당 옷이 없으면 넣고 카운트 1
            clothType.put(clothes[i][1], clothType.getOrDefault(clothes[i][1], 0) + 1);
        }

        // 조합을 센다. 옷 종류 별로 가지고 있는 옷갯수를 보자 추가로 옷종류 별로 안입을 경우의 수를 더한다.
        // 예를 들면 모자 2개 상의 3개 라고 한다면 모자로 나올수 있는 경우는 모자1, 모자2, 안입음 이렇게 3가지가 나온다.
        // 즉, 옷 종류에 있는 갯수 + 1을 해야 옷을 입는 경우의 수가 나온다.
        // 따라서 clothType.get(key) + 1 하고 answer에 곱해나가면 경우의수가 나온다. 이후 마지막에 - 1을 한다.(안입는 경우의수)
        for (String key:clothType.keySet()) {
            answer *= clothType.get(key) + 1;
        }
        // 아무것도 안입는 경우의 수 제거
        return answer - 1;
    }

}

- 옷 종류 별로 가지고 있는 옷의 갯수를 보자면 보통

모자 2개 상의 3개를 입는 경우의 수는 6이다.

하지만 모자를 안입고 상의를 안입는 경우까지 세자면 (2 + 1) * (3 + 1)  이렇게 된다.

그리고 아얘 안입는 경우를 빼면 - 1을 해주면된다.

 

따라서 옷을 입는 경우의수 만을 세면

*= (clothType.get(key) + 1)

 

마지막에 -1

4. Tip

- 경우의 수를 잘 세보자.

- 처음에 옷종류에 따른 옷갯수를 중복을 제외해서 구하기 위해 HashMap을 사용하고 getOrDefalut를 사용했다.