[프로그래머스 레벨2] 위장 : HashMap 사용(Java)

문제

 

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

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

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

 

 

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

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

입출력 예

clothes	return
[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crowmask", "face"], ["bluesunglasses", "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

 

 

-----------------------------------------------------------------------------------------------------------------------------------

 

난 문제를 보자마자 한 두시간동안 이걸 HashMap과 배열 비교하는걸로 해결하려 했다.

그리고 제한 사항으로 같은 이름을 가진 의상은 없다고 해서

나는 HashMap에다가 의상 이름을 Key값으로 넣었고 value 값으로 종류를 넣었다.

 

하지만 이렇게 한 세기간 혼자 헤매다가 이건 모든 경우의 수를 찾아야 된다는걸 깨달았다.

 

모든 경우의 수이니 각각의 경우를 구해야 한다.

그러기 위해선 일단 각각의 경우가 몇번 일어나는지 확인을 해야한다.

그래서 HashMap에다가 Key값으로 종류를 넣어야 한다.

 

Key값으로 종류를 넣고 나서부터는 경우의 수를 구하는 공식을 찾아다니기 시작했다.

 

위 문제는 일단 '곱의 법칙' 으로 해결해야한다.

왜냐하면 곱의 법칙은 '그리고' 가 들어갈때 사용하는데

 

'스파이는 모자를 쓰고 바지를 입어야 하기 때문이다.'

 

곱의 법칙을 구하는 방식은

일어날 사건들을 모두 구한다음 그 사건들의 경우의 수를 모두 곱하는것이다.

 

위 예제를 예를 들어 살펴보자.

 

[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]

 

여기서는 

 

headgear : 2번

eyewear : 1번 

 

이렇게 일어날 확률이 있다.

하지만 우리는 headgear를 쓰지 않았을때와 eyewear를 쓰지 않았을때를 더해주면

 

headgear : 3번

eyewear : 2번 

이렇게 된다.

 

그럼 각각의 사건이 나올 경우의수를 모두 구했으니 이제 이를 곱하면 된다.

 

3*2 = 6

 

6이 나왔는데 우리는 여기서 제한사항인

"스파이는 하루에 최소 한 개의 의상은 입습니다."

이를 만족하기 위해선 아예 벗고 다니는 경우의 수를 빼줘야 한다.

 

6-1 = 5

 

이렇게 해서 모든 조합의 수는 5개가 된다.

 

그럼 이제 소스를 보자.

 

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1; //곱셈을 하기 위해서
        
        HashMap<String,Integer> hm = new HashMap<>();
        //옷의 종류의 수를 count 하는 for문
        //count 한걸 집어 넣는 이유는 경우의 수를 구하기 위해서이다.
        //같은 종류 끼리는 중복 허용이 되지 않기 때문
        for(int i = 0; i<clothes.length;i++){
            //해당 키가 이미 존재 한다면진입
            if(hm.containsKey(clothes[i][1])){
                //+1을 한 이유는 이미 같은 종류가 존재하기 때문이다.
                hm.put(clothes[i][1],hm.get(clothes[i][1])+1);
            }else{ //해당키가 존재 않는다면 진입
                hm.put(clothes[i][1],1);
            }
        }
        System.out.println(hm);
        for(String s : hm.keySet()){
            answer *= hm.get(s) + 1; //+1을 한 이유는 쓰지 않았을때를 합하기 위해서다.
            
        }
        
        answer-=1; 
        // -1을 한 이유는 제한 사항에서 최소한 한개의 의상은 입는다그래서 안입은경우를 뺀것이다.
        
        return answer;
    }
}

 

위 문제도 마찬가지로 답을 보고 소스를 이해했다.

 

느낀점

1. 문제를 자세히 살펴보고 문제가 뭘 원하는지부터 찾자.

2. HashMap에다가 Key값을 넣을땐 어떤 값을 넣어야 하는지 곰곰히 생각해보자.

3. 한문제에 3시간 이상 지체하면 바로 답을 확인해보자.

 

 

 

참고 사이트 : https://youtu.be/_Tkq_XC3slw