프로그래머스 | 의상

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

프로그래머스

 

 

문제 설명

clothes의 각 행이 [의상 이름, 의상 종류]로 주어질 때, 의상의 종류가 겹치지 않게 입을수 있는 경우의 수 구하기

단, 의상의 이름이 겹치는 경우는 없다.

 

내가 생각했던 풀이법

먼저 의상의 종류가 겹치지 않고, 입을수 있는 경우의 수만 구하는 것 이라면 의상의 이름은 중요치 않다.

 

이 문제의 분류가 해시로 되어있었으므로 이를 활용하여 의상종류별로 구별해서 개수를 세면 될 것 같다.

[종류 : 개수] 이러한 꼴로 분류를 하면 될 것 같다.

 

입출력 예 1번을 확인해보면

[headgear : 2] , [eyewear : 1] 로 해시맵을 작성 할 수 있다.

 

이후 내가 생각한 방식은

1. 모두 1번씩은 입을수 있다 -> 2 + 1 = 3

2. 중복되지 않은 옷끼리 한번씩 더 입을수 있다 -> 2 * 1 = 2

3. 이를 모두 합하면 3+2 = 5 가 되므로 정답은 5이다.

 

하지만 이 방식에는 오류가 있는데 만약 종류가 3종류 이상 늘어난다면 계산이 매우 복잡해진다는 문제가 있었다.

또한, 만약 예제 2번처럼 종류가 1개 밖에 없다면 어떻게 처리할 것인가에 대해서도 생각해야한다.

 

그렇다면 비트처럼 계산해보면 되지않을까 해서 생각을 조금 바꿔봤다.

첫번째 예제를 예로 들면 이러한 꼴이 된다.

 

headgear = [off,on,on]

eyewear = [off,on]

 

off는 모두 벗는것을 의미하고 on은 그것 하나만 입는것을 의미한다.

하지만 어느 한부위라도 무조건 입고 있어야 하므로 -1을 해줘야한다.

그래서 (n+1) * (m+1) -1 이라는 식이 나오게 된다.

 

이렇게 한다면 가능한 모든 경우의 수를 계산하고, 모두 벗은 상태를 제거함으로써 정답이 된다.

이것을 java로 구현해보았다.

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 0;
        String temp = "";
        HashMap<String,Integer> hash = new HashMap<>();
        
        // 1. 옷의 종류별로 분류한다.
        for(int i = 0; i < clothes.length;i++){
            temp = clothes[i][1];
            hash.put(temp,hash.getOrDefault(temp,0)+1);
        }
        
        // 2. 만약 의상 종류가 한개밖에 없다면 해당 의상의 개수를 반환한다.
        if (hash.size() == 1) {
            answer = clothes.length;
        } else {
        // 3. 두개 이상이면 반복문을 실행하여 value값을 가져온다.
            for(Integer value : hash.values()){
                if (answer == 0){
                	// 초기값 할당
                    answer = value + 1;
                }else{
                	// value값에 1을 더하고 곱한 값을 할당
                    answer *= (value + 1);
                }
            }
            // 최종 결과에서 -1
            answer -= 1;
        }
        return answer;
    }
}