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

문제 링크

코딩테스트 연습 - 위장 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 위장

 

문제 설명

스파이는 가지고 있는 옷을 조합해서 입습니다. 하지만 적어도 하나의 옷은 입어야 하며 같은 종류의 옷은 중복해서 입지 못합니다. 한 부위의 옷은 하나만 입어야 한다는 뜻입니다.

매개변수 clothes[][] 에서는 옷의 종류와 각 종류에 해당하는 옷들을 알 수 있습니다. 서로 다른 옷의 조합의 수를 구하면 되는 문제입니다.

 

풀이

옷의 종류를 Key, 옷들을 Value 로 가지는 해시맵을 이용합니다.

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

 

 

map

key	value
얼굴	A, B, C
상의	D, E
하의	F

스파이가 위 예시처럼 3종류의 옷과, 각 종류마다 3 , 2, 1 벌의 옷을 가지고 있다고 합시다.

얼굴: 3 , 상의: 2, 하의: 1

입을 수 있는 옷의 조합의 수는 어떻게 될까요?

 

1. 1개 : (얼굴), (상의), (하의) = 3 + 2 + 1 = 6가지

2. 2개 : (얼굴,상의) (얼굴,하의) (상의,하의) = 6 + 3 + 2 = 11가지

3. 3개 : (얼굴,상의,하의) = 6가지

총 갯수 : 6 + 11 + 6 = 23가지 입니다.

 

이렇게 순서쌍을 일일이 구할수도 있지만, 그렇게 되면 숫자가 커지면 너무나 복잡해집니다.

얼굴: 3 , 상의: 2, 하의: 1

위 값들을 모두 곱하면 6가지로, 3.번인 얼굴, 상의, 하의를 모두 한개씩 조합한 경우만 해당되지만 우리가 원하는 답은 아닙니다.

 

key	value
얼굴	A, B, C, X
상의	D, E, X
하의	F, X

위처럼 각 종류에 X (= 無) 를 뜻합니다. 없다는 뜻이죠

이제 각각 곱하면 (4 x 3 x 2) = 24 는 A~F, X 를 포함한 순서쌍의 갯수입니다. 이렇게 되면 모든 경우의 수를 구할 수 있습니다.

 

여기서 주의할점은 스파이가 적어도 하나의 옷은 입어야 된다고 문제에 나와있으므로,

(X,X,X) : 아무것도 입지 않은 경우 를 빼줘야 합니다.

 

따라서 정답은 24 -1 =23 이 됩니다.

위처럼 종류별 옷의 개수에 1씩을 더해서 (+ X) 모두 곱한 뒤에 1을 빼주면 됩니다. 1을 빼는 이유는 아무것도 입지 않은 경우 한가지를 제외하는 것입니다.

 

 

 

소스코드

public int solution(String[][] clothes) {
    int answer = 1;
    Set<String> set = new HashSet<>();
    Map<String, ArrayList<String>> map = new HashMap<>();
    for (String[] s : clothes) {
        ArrayList<String> temp = map.getOrDefault(s[1], new ArrayList<>());
        temp.add(s[0]);
        map.put(s[1], temp);
        set.add(s[1]);
    }

    for (String s : set) {
        ArrayList<String> list = map.get(s);
        answer *= list.size()+1;
    }

    return answer-1;
}