[JAVA] 프로그래머스 - 위장

programmers.co.kr/learn/courses/30/lessons/42578

코딩테스트 연습 - 위장

 

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 0;
        Set<String> set = new HashSet<>(); // 물건들의 종류를 위한 HashSet
        
        for(int i=0; i<clothes.length; i++) // 물건들을 set에 추가하며 종류를 추린다.
            set.add(clothes[i][1]);
        
        if(set.size() == 1) //물건의 종류가 하나면 해당 물건들의 길이를 리턴
            return clothes.length;
        
        int total = 1;
        int cnt;
        /*
        headgear1 headgear2
        0           x
        x           0
        x           x
        한 종류 내에 다수의 물건이 있을 경우의 수이다.
        */
        for(String str : set){ // 물건의 종류별로 순회
            cnt=0;
            for(int j=0; j<clothes.length; j++){ // 각 종류의 물건의 개수를 카운트한다.
                if(str.equals(clothes[j][1]))
                  cnt++;
            }
            total *= (cnt+1); // 한 종류의 물건들의 개수에 +1 값을 누적해 곱한다.
        }
        return total-1; // 가장 마지막에 모든 물건들이 선택되지 않은 경우를 리턴
    }
}

 

경우의 수를 생각해 풀면 그리 어렵지 않은 문제였다.

각 종류마다 나올 수 있는 경우의 수를 도출하고 각 경우의 수를 모두 곱한 값을 리턴하면 되는 문제였다.

 

문제의 핵심은

 

모든 물건 중 최소한 하나는 착용해야 한다는 것.

같은 종류의 물건은 동시에 2개 이상 착용할 수 없다는것.

이었다.

 

한 종류에서 나올 수 있는 경우의 수를 생각해보자.

Headgear 1	Headgear 2
O	X
X	O
X	X

각 물건을 한번씩 착용하는 경우 = 물건의 길이

아무것도 착용하지 않는 경우 = 1

합 = 물건의 길이 + 1

 

그래서 모든 종류의 (길이 + 1) 값을 곱한 후

모든 물건의 선택되지 않은 경우인 1개의 경우를 빼주면 정답이 리턴된다.

 

각 물건 종류의 합을 구하는 과정에서 최적화를 더 한다면 시간을 더 단축시킬 수 있겠다.