[프로그래머스,Java] Levle2: 위장

 

문제분석

 

목표: 스파이가 위장을 할수있는 경우의 수를 구하시오.

 

주어지는 입력:  [의상의 이름, 의상의 종류] 형식으로 주어지는 clothes

 

 

위 사진의 표를 보면,   종류와 이름이  너무 이쁘게 Key , Values로 나누어져 있지않나요?

 

주어지는 입력들도 Key, Value형식으로도 마침 주었고요.

 

그래서 필자는 적극적으로 Map(HashMap)을 사용했습니다.

 

Key : 의상의 종류  , Value : 의상의 이름을 담는 리스트

 

Map에 정보를 입력할때, 2가지 분기를 나누어줫습니다.

 

1. 의상의 종류가 없을때

-> 새로운 리스트를 생성한뒤, 의상의 이름을 담아 넣어준다.

 

2.의상의 종류가 이미 있을때

->그 의상의 종류의 의상리스트를 가져와, 새로운 의상을추가해 다시 넣어준다.

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

여기까지는 어렵지 않습니다.

 

남은건 갯수를 세주는 일인데요, 스파이는 최소 1가지 옷을 입고 위장합니다.

 

예를들어, 종류가 4가지라면..

 

4C1 개를 골라, 의상수를 더해주고,

4C2 개를 골라, 골라진 의상종류의 의상수를 곱해서 더해주고,

4C3 개를 골라, 골라진 의상종류의 의상수를 곱해서 더해주고,

4C4 개를 골라, 골라진 의상종류의 의상수를 곱해서 더해줘야합니다.

 

->특수 로직을 모르면 이 과정을 거쳐야합니다..

 

 

하지만, 이 문제를 아주 쉽게 푸는 수식이 존재합니다.

 

바로, Map의 저장된 의상 종류마다 가진 의상수를 +1 한뒤 모두 곱하고 -1을하면 모든 갯수가나옵니다.

 

이 공식이 일치하는 이유가 뭘까요?

 

의상수에서 +1은 [공백] 이라는 의미입니다.   공백을 고르면 그 의상의 종류는 입지 않겠다 라는뜻입니다.

 

예를들어 얼굴 종류의 공백과 , 상의 종류의 의상을 하나 고르면 상의 하나만 입은걸로 볼 수 있습니다.  

 

그렇다면 마지막에 -1은 왜할까요?

 

모든 의상종류마다 전부다 [공백]을 골랐다고 가정합시다.

스파이는 최소 1가지 옷은 입어야하는 경우에 위배대는 경우가 딱 하나 존재하게됩니다.

 

따라서, (A+1)(B+1)(C+1)...(N+1) - 1 의 공식이 성립하게 되는겁니다.

 

문제풀이

import java.util.*;
class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        Map<String,List<String>> map = new HashMap<>();
        
        for(String[] data: clothes){
            if(map.containsKey(data[1])){
                 List<String> list= map.get(data[1]);
                 list.add(data[0]);
                 map.put(data[1],list);
            }
            else{
                List<String> list1= new ArrayList<>();
                list1.add(data[0]);
                map.put(data[1],list1);
            }
        }
        
        //공식 대입
        for(String data:map.keySet()){
            List<String> temp = map.get(data);
            answer*=temp.size()+1;
        }
        
        return answer-1;
    }
 
}