프로그래머스_의상_day17

프로그래머스 알고리즘 챌린지 17일 차이다. 오늘도 level2에 분류된 자료구조 문제를 가져와 보았다. 
문제를 읽다보니 분명히 풀었던 문제인 것 같은데, 안 푼문제로 분류되어 있어서 뭐지 하고 풀었다. 
문제를 다 풀어보고 나니 취업준비 기간 때 같이 학원 다니던 친구가 질문했던 문제였었다는 게 떠올랐다. 

그때 당시에는 생각보다 쉽게 풀이해서 설명해줬었는데 이번엔 그러지 않은 것을 보니 확실히 감이 많이 죽은 것 같다. 

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

프로그래머스

 

문제 분류에 해시라고 나와있는 것을 보고 map을 써야 겠다는 점을 떠올릴 수 있을 것이다. 
무엇인가 떠오르지 않을때는 역시 작은 경우의 수에 대해서 손으로 써보는 것이 가장 좋다. 

예를 들어 face, head_gear, eye_wear 이렇게 세 가지 종류가 각각 3, 2, 1개씩 있다고 가정해 보자. 

겹치지 않게 의상을 코디하는 방법을 조합하는 과정은 아래와 같다. 

	face	head_gear	eye_wear
1가지 종류로만 코디	3	2	1
2가지 종류로만 코디	face * head_gear + head_gear * eye_wear + eye_wear * face
3가지 종류로만 코디	face * head+gear * eye_wear

코니는 반드시 하나의 옷을 입기 때문에 서로 다른 옷을 입는 경우의 수를 구하기 위해서는 위와 같이 복잡하게 구해야 한다. 일일이 사람이 계산하기에는 어렵지 않지만 컴퓨터가 계산하기 위해서는 일반화된 식을 전달해 주어야 자동화해서 계산을 해줄 텐데 특별한 규칙도 보이지 않는다. 

이런 경우 어떡하지? 라는 생각을 하지 말고 관점을 반대로 바꾸어 보자. 
위의 표는 옷을 입는 경우를 중심으로 생각하고 있는데 옷을 입지 않는 경우를 기준으로 생각해보자.

각 경우의 수를 쪼개어서 살펴보면,
1가지 종류로만 코디하는 경우 face하나를 착용할 때는 head_gear와 eye_wear는 안 입은 상태이다. 
2가지 종류로만 코디하는 경우 face와 head_gear를 착용할 때는 eye_wear는 안 입은 상태이다. 

이런 식으로 조합의 대상에 '안 입음'상태를 추가해 주자는 것이다. 정리하면 아래와 같다. 

face	f1	f2	f3	안 입음
head_gear	h1	h2	안 입음
eye_wear	e1	안 입음

위처럼 생각하면서 각 종류별로 한 가지 경우의 수를 골라 조합하는 경우의 수는 4 * 3 * 2가 된다. 

이때 하나만 예외 조건을 고려해 주면 되는데, 바로 모두 '안 입음'상태로 구성된 조합이다. 
적어도 하나의 옷은 입는다고 했으니 이 한 가지 경우의 수를 빼주면 된다. 

문제가 풀리지 않을 때는, 내가 지금 중심적으로 바라보고 있는 핵심 기준을 반대로 뒤집어서 생각해 보자. 
그러면 웬만해서 실마리를 잡을 수 있고, 그 경우 반드시 반례 혹은 예외가 존재하기 때문에 이 점을 놓치지 말자. 

 

Java

import java.util.*;
class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        Map<String, Integer> map = new HashMap<>();
        for (String[] temp : clothes) {
            map.put(temp[1], map.getOrDefault(temp[1], 1) + 1);
        }
        
        for(Map.Entry<String, Integer> m : map.entrySet()) {
            answer *= m.getValue();
        }
        return answer-1;
    }
}