[코테연습] 의상

 

오늘은 해시 - 의상 코딩테스트 문제를 풀었다.

이미 전에 풀어본 문제였기 때문에 쉽게 접근할 수 있었던 문제였다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

 

 

해당 문제의 키포인트는 각 의상의 종류별로 의상을 구한 뒤에, 전체 경우의 수를 구하는 것이다.

 

예를 들어

[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]

를 

 

["yellow_hat", "headgear"],

["green_turban", "headgear"]

 

 ["blue_sunglasses", "eyewear"], 

 

로 구분하여 

headgear 2개, eyewear 1개로 분류하여 갯수를 구했더라도 '입지 않는 경우' 의 경우의 수를 생각해내고, 코드로 구현하지 못한다면 어려운 문제로 다가온다.

 

headgear 2개 + 입지않은 경우 1개 = 3개

eyewear 1개 + 입지않은 경우 1개 = 2개

 

를 구한 뒤에,

 

3 * 2 를 해야 입지 않은 경우를 포함한 전체 경우의 수를 구할 수 있다.

그리고 필연적으로 하나도 입지 않은 경우 ( [[],[]] ) 가 발생하는데, 이것은 전체 경우의 수 중 하나의 경우에 해당하므로 빼주면 될 것이다.

 

즉,

3 * 2 - 1 = 5 

5가지 경우의 수를 구할 수 있다.

 

해당 사항을 코드로 구현하면 다음과 같다. 

 

 public int solution(String[][] clothes) {

        int answer = 1;

        //각 의상을 의상의 종류 별로 분류한다

        Map<String, List<String>> map = new HashMap<>();

        for (int i = 0; i < clothes.length; i++) {

            String value = clothes[i][0];//value

            String key = clothes[i][1];//key

            List<String> list = map.get(key) == null ? new ArrayList<>() : map.get(key);

            list.add(value);

            map.put(key, list);

        }

        System.out.println(map);

        //전체 경우의 수를 구하기 위해서 각 의상의 종류 length 값에 걸치지 않은 경우의 수를 더한다

        for(String key : map.keySet()) {

            int length = map.get(key).size()+1;

            answer*=length;

        }

        //아무것도 걸치지 않는 경우를 포함하여 각 의상의 종류를 구한다

        answer -= 1;

        System.out.println("sum : "+answer);

        return answer;

    }